Hiểu bài toán

Bài toán yêu cầu tính giá trị của tổ hợp chập k của n, ký hiệu là C(n, k) hoặc nCk, với điều kiện 0 ≤ k ≤ n ≤ 2000. Kết quả có thể rất lớn (lên đến hàng nghìn chữ số) nên không thể lưu vào kiểu dữ liệu số nguyên thông thường. Do đó, cần sử dụng các kỹ thuật như kiến trúc số lớn (big integer) hoặc phân tích thừa số nguyên tố để tính toán chính xác.

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

Cách Dùng chuỗi (Big Integer) - Nhân và Chia

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>

using namespace std;

string multiply(string a, int b) {
    string res = "";
    int carry = 0;
    for (int i = a.size() - 1; i >= 0; i--) {
        int prod = (a[i] - '0') * b + carry;
        res += (prod % 10) + '0';
        carry = prod / 10;
    }
    while (carry) {
        res += (carry % 10) + '0';
        carry /= 10;
    }
    reverse(res.begin(), res.end());
    return res;
}

string divide(string a, int b) {
    string res = "";
    int idx = 0;
    int temp = a[idx] - '0';
    while (temp < b) {
        temp = temp * 10 + (a[++idx] - '0');
    }
    while (idx < a.size()) {
        res += (temp / b) + '0';
        temp = (temp % b) * 10 + a[++idx] - '0';
    }
    if (res.empty()) return "0";
    return res;
}

int main() {
    int n, k;
    cin >> k >> n;
    if (k > n - k) k = n - k;
    string res = "1";
    // C(n, k) = (n * (n-1) * ... * (n-k+1)) / (1 * 2 * ... * k)
    for (int i = 0; i < k; i++) {
        res = multiply(res, n - i);
    }
    for (int i = 1; i <= k; i++) {
        res = divide(res, i);
    }
    cout << res << endl;
    return 0;
}

• Time Complexity: O(k * L), với L là độ dài số lớn (tối đa ~6000 chữ số). Với n=2000, k=1000, đây là cách làm chấp nhận được.
• Space Complexity: O(L) để lưu số lớn.

Phương pháp này tính trực tiếp công thức C(n,k) = (n(n-1)...(n-k+1))/(12...k). Để tránh số quá lớn trong quá trình nhân, ta có thể thực hiện phép chia ngay khi nhân hoặc dùng chuỗi để lưu trữ. Code mẫu dùng chuỗi: nhân dãy số trên, rồi chia dãy số dưới. Tuy nhiên, để tối ưu hơn và tránh tràn số, một biến thể tốt hơn là vừa nhân vừa chia ngay lập tức (VD: res = res * (n-i) / (i+1)) nhưng phải đảm bảo chia hết. Code trong giải pháp 1 và 2 minh họa cách dùng chuỗi để nhân và chia, hoặc dùng mảng phân tích thừa số nguyên tố.

Cách Phân tích thừa số nguyên tố (Prime Factorization)

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

string multiply(string s, int n) {
    string res = "";
    int carry = 0;
    for (int i = s.size() - 1; i >= 0; i--) {
        int x = (s[i] - '0') * n + carry;
        res = to_string(x % 10) + res;
        carry = x / 10;
    }
    if (carry) res = to_string(carry) + res;
    return res;
}

int main() {
    int n, k;
    cin >> k >> n;
    if (k > n - k) k = n - k;

    vector<int> tu_so;
    for (int i = n - k + 1; i <= n; i++) tu_so.push_back(i);

    // Phân tích các thừa số chung và loại bỏ
    for (int i = 2; i <= k; i++) {
        int tmp = i;
        for (auto &x : tu_so) {
            int g = __gcd(tmp, x);
            x /= g;
            tmp /= g;
            if (tmp == 1) break;
        }
    }

    string res = "1";
    for (auto x : tu_so) {
        if (x > 1) res = multiply(res, x);
    }
    cout << res << endl;
    return 0;
}

• Time Complexity: O(k^2 * L) hoặc tốt hơn depending on GCD. Với n=2000, k=1000, số lượng thao tác nhỏ.
• Space Complexity: O(k) để lưu dãy số.

Công thức C(n,k) = [n(n-1)...(n-k+1)] / [k(k-1)...1]. Ta tính tử số và mẫu số riêng. Để tránh tràn số, ta đưa các số trong tử số và mẫu số vào hai list hoặc mảng. Sau đó, dùng hàm GCD (ƯCLN) để rút gọn phân số trước khi nhân. Ví dụ, thay vì nhân cả 2000/1000, ta chia chung cho ước chung. Cuối cùng chỉ cần nhân các số còn lại trong tử số. Code mẫu dùng vector lưu các số trong tử số, rồi lần lượt chia cho các số từ 2 đến k để loại bỏ thừa số chung.

Cách Dynamic Programming (Bảng Pascal)

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

string add(string a, string b) {
    string res = "";
    int carry = 0;
    int i = a.length() - 1;
    int j = b.length() - 1;
    while (i >= 0 || j >= 0 || carry) {
        int sum = carry;
        if (i >= 0) sum += a[i--] - '0';
        if (j >= 0) sum += b[j--] - '0';
        res += to_string(sum % 10);
        carry = sum / 10;
    }
    reverse(res.begin(), res.end());
    return res;
}

int main() {
    int n, k;
    cin >> k >> n;
    if (k > n - k) k = n - k;

    vector<string> C(k + 1, "0");
    C[0] = "1";

    for (int i = 1; i <= n; i++) {
        for (int j = min(i, k); j > 0; j--) {
            C[j] = add(C[j], C[j-1]);
        }
    }

    cout << C[k] << endl;
    return 0;
}

• Time Complexity: O(n * k * L). Với n, k <= 2000, độ dài số L có thể lên tới 6000. Số phép toán ~ 2000*2000*6000 ~ 24 tỷ, quá chậm cho C++.
• Space Complexity: O(k * L).

Sử dụng tính chất C(n, k) = C(n-1, k) + C(n-1, k-1). Ta xây dựng bảng Pascal. Tuy nhiên, do kết quả là số lớn, ta phải dùng string để cộng. Độ phức tạp O(nkL) khiến phương pháp này quá chậm cho n=2000 trong thời gian giới hạn của OJ (thường là 1-2s). Nó chỉ khả thi cho n nhỏ hơn nhiều.

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

Bài học kinh nghiệm

• Kiểu dữ liệu integer thông thường (64-bit) không đủ lưu kết quả C(2000, 1000) (~600 chữ số). Phải dùng string (Big Integer).
• Phép chia phải được thực hiện cẩn thận để đảm bảo kết quả là số nguyên (không dư số), có thể dùng GCD để rút gọn trước.
• Phân tích thừa số nguyên tố hoặc tối ưu hóa công thức là cách hiệu quả nhất để giảm thiểu số lượng thao tác với số lớn.

Lỗi thường gặp

• Làm tròn số khi thực hiện phép chia trong quá trình nhân/chuỗi nếu không dùng hàm chia đúng cho số lớn.
• Quên điều kiện k > n - k để tối ưu (C(n, k) = C(n, n-k)), dẫn đến chạy chậm hơn.
• Sử dụng thuật toán DP bảng Pascal với số lớn cho n=2000 chắc chắn bị TLE (Time Limit Exceeded) vì độ phức tạp quá cao.