Hiểu bài toán

Bài toán yêu cầu tính giá trị tổ hợp chập k của n, ký hiệu là C(n, k) hay "n chập k". Với các ràng buộc 1 ≤ k ≤ n ≤ 1000, giá trị của C(n, k) có thể rất lớn. Do đó, bài toán yêu cầu in ra kết quả sau khi lấy số dư modulo với 10^9 + 7. Tên đề bài là "Tính hệ số nhị thức".

Các cách tiếp cận

Cách Quy hoạch động Pascal

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

const int MOD = 1e9 + 7;
int C[1001][1001];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int k, n;
    cin >> k >> n;

    // Khởi tạo mảng C để tính tổ hợp
    for (int i = 0; i <= n; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= i; j++) {
            C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
        }
    }

    cout << C[n][k] << "\n";
    return 0;
}

• Time Complexity: O(n^2)
• Space Complexity: O(n^2)

Phương pháp này dựa trên công thức Pascal: C(n, k) = C(n-1, k-1) + C(n-1, k). Ta xây dựng một bảng 2 chiều (ma trận) trong đó C[i][j] lưu trữ giá trị tổ hợp C(i, j). Bằng cách duyệt qua các hàng từ 0 đến n và các cột tương ứng, ta có thể tính toán tất cả các giá trị tổ hợp cần thiết. Với n tối đa là 1000, độ phức tạp O(n^2) hoàn toàn chấp nhận được. Phương pháp này thường được gọi là thuật toán Pascal.

Cách Công thức giai thừa với nghịch đảo modulo

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9+7;

ll modpow(ll a, ll e){
    ll r = 1;
    while(e){
        if(e & 1) r = r * a % MOD;
        a = a * a % MOD;
        e >>= 1;
    }
    return r;
}

int main(){
    int k, n; if(!(cin >> k >> n)) return 0;
    vector<ll> f(n+1); f[0]=1;
    for(int i=1;i<=n;i++) f[i] = f[i-1]*i % MOD;
    ll denom = f[k]*f[n-k] % MOD;
    cout << f[n] * modpow(denom, MOD-2) % MOD;
}

• Time Complexity: O(n + log MOD)
• Space Complexity: O(n)

Phương pháp này sử dụng công thức toán học: C(n, k) = n! / (k! * (n-k)!). Trong trường hợp số học modulo, phép chia không tồn tại trực tiếp. Thay vào đó, ta nhân với số nhân nghịch đảo (modular inverse). Do MOD là số nguyên tố (10^9 + 7), ta có thể tính số nhân nghịch đảo của k! và (n-k)! bằng định lý Fermat nhỏ (a^(MOD-2) ≡ a^(-1) mod MOD). Ta tính trước giai thừa modulo cho các số từ 0 đến n, sau đó tính kết quả bằng cách nhân giai thừa của n với số nhân nghịch đảo của mẫu số.

Cách Tính trực tiếp với truy xuất giai thừa

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

const long long MOD = 1e9 + 7;

long long mod_pow(long long x, long long y, long long mod) {
    long long res = 1;
    x %= mod;
    while (y) {
        if (y & 1) res = res * x % mod;
        x = x * x % mod;
        y >>= 1;
    }
    return res;
}

long long factorial_mod(int n, long long mod) {
    long long res = 1;
    for (int i = 2; i <= n; i++)
        res = res * i % mod;
    return res;
}

int main() {
    int n, k;
    cin >> k >> n;

    long long fact_n = factorial_mod(n, MOD);
    long long fact_k = factorial_mod(k, MOD);
    long long fact_nk = factorial_mod(n - k, MOD);

    long long inv = mod_pow(fact_k * fact_nk % MOD, MOD - 2, MOD);

    long long C = fact_n * inv % MOD;

    cout << C << "\n";
    return 0;
}

• Time Complexity: O(n + log MOD)
• Space Complexity: O(1)

Đây là biến thể của phương pháp giai thừa. Thay vì lưu trữ mảng giai thừa cho tất cả các số từ 0 đến n, ta chỉ tính giai thừa tại các điểm cần thiết: n!, k!, và (n-k)!. Điều này giúp tiết kiệm bộ nhớ đáng kể (giảm từ O(n) xuống O(1)), mặc dù độ phức tạp thời gian vẫn tương đương. Phương pháp này phù hợp khi n rất lớn nhưng ta chỉ cần tính một giá trị C(n, k) duy nhất.

Phân tích độ phức tạp

Bài học kinh nghiệm

• MOD là số nguyên tố (10^9 + 7), cho phép sử dụng số nhân nghịch đảo thông qua công thức lũy thừa (Fermat's Little Theorem).
• Với n nhỏ (≤ 1000), quy hoạch động Pascal là cách tiếp cận trực quan và dễ cài đặt nhất.
• Sử dụng long long là cần thiết để tránh tràn số khi thực hiện các phép nhân trước khi lấy modulo.

Lỗi thường gặp

• Quên lấy modulo sau mỗi phép nhân hoặc phép cộng, dẫn đến tràn số (integer overflow) vì 1000! rất lớn.
• Sử dụng biến int cho các biến lưu trữ kết quả trung gian trong phép nhân.
• Không khởi tạo giá trị cơ sở cho quy hoạch động (ví dụ: C[i][0] = 1).