Đếm hoán vị giảm rồi tăng của các số từ 1 đến num trong C++

Cho biến num. Mục tiêu là đếm số hoán vị của các số trong khoảng [1, num] mà các số đầu tiên giảm dần sau đó tăng dần. Ví dụ num=3, các số là 1,2,3. Các hoán vị thỏa mãn: [3,1,2] và [2,1,3], kết quả là 2.

Trong mọi hoán vị, điểm chuyển từ giảm sang tăng được quyết định bởi vị trí của số 1 (số nhỏ nhất). Sau số 1, các số sẽ bắt đầu tăng. Để hoán vị giảm rồi tăng, số 1 phải nằm ở vị trí từ 2 đến num-1.

• Nếu 1 ở đầu → dãy tăng hoàn toàn.
• Nếu 1 ở cuối → dãy giảm hoàn toàn.

Với num=4:

• Đặt 1 ở vị trí 2: [-, 1, -, -]. Vị trí 1 chọn từ {2,3,4} → 3C1 hoán vị.
• Đặt 1 ở vị trí 3: [-, -, 1, -]. Chọn 2 số cho 2 vị trí đầu từ {2,3,4} → 3C2 hoán vị.

Với num=x bất kỳ: count = (x-1)C1 + (x-1)C2 + ... + (x-1)C(x-2) = 2^(x-1) - 2 (theo định lý nhị thức).

Ví dụ

Đầu vào − num = 4

Đầu ra − 6

Giải thích − Các hoán vị:

[2,1,3,4], [3,1,2,4], [4,1,2,3] → 1 ở vị trí 2
[2,3,1,4], [2,4,1,3], [3,4,1,2] → 1 ở vị trí 3

Đầu vào − num = 6

Đầu ra − 30

Phương pháp giải

Sử dụng định lý nhị thức để tính trực tiếp: count = 2^(num-1) - 2. Tạo hàm value(long long i, long long num) tính i^num % MOD với MOD = 1000000007.

• Nhận num.
• Hàm permutations_increase_decrease(int num) trả về kết quả.
• Hàm value(i, num) tính lũy thừa nhanh modulo 1000000007.
• Nếu num == 1 trả về 0.
• Ngược lại: count = (value(2, num-1) - 2) % MOD.
• Trả về count.

Ví dụ code

#include <bits/stdc++.h>
using namespace std;

long long value(long long i, long long num) {
    int MOD = 1000000007;
    if (num == 0) return 1;
    long long j = value(i, num / 2) % MOD;
    j = (j * j) % MOD;
    if (num & 1) j = (j * i) % MOD;
    return j;
}

int permutations_increase_decrease(int num) {
    int MOD = 1000000007;
    if (num == 1) return 0;
    int count = (value(2, num - 1) - 2) % MOD;
    return count;
}

int main() {
    int num = 4;
    cout << "Count of permutations that are first decreasing then increasing are: " << permutations_increase_decrease(num);
    return 0;
}

Đầu ra

Count of permutations that are first decreasing then increasing are: 6