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) hoặc nCk, với k và n có thể lên tới 1,000,000. Kết quả cần phải được in ra dưới dạng số dư khi chia cho 10^9 + 7. Do giới hạn về độ lớn của n, các phép tính phải được thực hiện trong thời gian ngắn và sử dụng số học modulo.

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

Cách Công thức lặp (Iterative Formula)

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

const int MOD = 1e9 + 7;

long long power(long long a, long long b) {
    long long res = 1;
    while (b > 0) {
        if (b & 1) res = (res * a) % MOD;
        a = (a * a) % MOD;
        b >>= 1;
    }
    return res;
}

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

    // C(n, k) = n! / (k! * (n-k)!)
    // C(n, k) = (n * (n-1) * ... * (n-k+1)) / k!

    long long numerator = 1;
    for (int i = 0; i < k; i++) {
        numerator = (numerator * (n - i)) % MOD;
    }

    long long denominator = 1;
    for (int i = 1; i <= k; i++) {
        denominator = (denominator * i) % MOD;
    }

    long long result = (numerator * power(denominator, MOD - 2)) % MOD;
    cout << result;

    return 0;
}

• Time Complexity: O(k log MOD)
• Space Complexity: O(1)

Phương pháp này tính trực tiếp C(n, k) bằng cách nhân các số từ n giảm dần xuống n-k+1 cho tử số, và nhân các số từ 1 đến k cho mẫu số. Phép chia trong modulo thực chất là nhân với số nghịch đảo (modular inverse) của mẫu số, được tính bằng định lý Fermat nhỏ (a^(MOD-2) mod MOD). Phương pháp này không cần precompute mảng factorial nên tiết kiệm bộ nhớ.

Cách Precompute Factorial

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1e9 + 7;
const int MAX = 1e6 + 5;

vector<long long> fact(MAX);
vector<long long> inv_fact(MAX);

long long power(long long a, long long b) {
    long long res = 1;
    a %= MOD;
    while (b > 0) {
        if (b % 2 == 1) res = (res * a) % MOD;
        a = (a * a) % MOD;
        b /= 2;
    }
    return res;
}

void precompute() {
    fact[0] = 1;
    for (int i = 1; i < MAX; i++) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }
    inv_fact[MAX - 1] = power(fact[MAX - 1], MOD - 2);
    for (int i = MAX - 2; i >= 0; i--) {
        inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % MOD;
    }
}

long long comb(int n, int k) {
    if (k < 0 || k > n) return 0;
    return (fact[n] * inv_fact[k] % MOD) * inv_fact[n - k] % MOD;
}

int main() {
    precompute();
    int k, n;
    cin >> k >> n;
    cout << comb(n, k) << endl;
    return 0;
}

• Time Complexity: O(MAX) để precompute, O(1) cho mỗi truy vấn
• Space Complexity: O(MAX)

Phương pháp này precompute (tính trước) giai thừa và số nghịch đảo của giai thừa cho tất cả các số từ 0 đến MAX. Khi nhận input, chỉ cần truy cập mảng đã tính sẵn và thực hiện phép nhân. Đây là phương pháp hiệu quả nhất nếu có nhiều truy vấn hoặc n rất lớn. Việc tính số nghịch đảo giai thừa.backward (từ MAX về 0) giúp tiết kiệm thời gian tính toán power so với việc gọi power cho mỗi phần tử.

Cách Mathematics Formula (No Modulo)

#include <iostream>
using namespace std;

int main() {
    int k, n;
    cin >> k >> n;
    // This approach only works if result fits in standard integer types
    // and no modulo is required. 
    // Since problem requires modulo, this is just a conceptual placeholder.
    // Real implementation would need BigInt or similar if modulo wasn't required.
    // But given constraints up to 1e6, result is astronomically large.
    // Therefore, this approach is NOT viable for the given problem constraints.
    return 0;
}

• Time Complexity: N/A
• Space Complexity: N/A

Đây là một phương pháp giả định (thường chỉ dùng cho số nhỏ) không sử dụng modulo. Với n lên tới 1,000,000, kết quả C(n, k) sẽ vượt quá khả năng lưu trữ của bất kỳ kiểu dữ liệu nguyên nào (kể cả 128-bit). Do đó, phương pháp này không thể sử dụng cho bài toán này trừ khi áp dụng thuật toán BigInt, nhưng việc yêu cầu số dư cho thấy phương pháp số học modulo (như Approach 1 và 2) là bắt buộc.

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

Bài học kinh nghiệm

• Sử dụng số học modulo: Phép chia a/b (mod M) tương đương với a * b^(M-2) (mod M) dựa trên định lý Fermat nhỏ khi M là số nguyên tố.
• Kiểm tra điều kiện biên: Nếu k > n, kết quả phải là 0.
• Tối ưu tính toán: Precomputing factorial giúp giảm thời gian thực thi đáng kể cho các bài toán nhiều truy vấn.

Lỗi thường gặp

• Quên xử lý số âm hoặc tràn số khi thực hiện phép nhân modulo (sử dụng long long là bắt buộc).
• Sai công thức tính số nghịch đảo modular (Fermat's Little Theorem chỉ áp dụng khi M là số nguyên tố).
• Biến overflow trong vòng lặp tính toán nếu không dùng phép chia lấy dư thường xuyên.