Tóm tắt đề bài

Cho hai số nguyên \(n, k\) với \(k < n < 10^9+7\). Hãy tính tổ hợp

theo modulo \(M = 10^9+7\) (là số nguyên tố).

Phân tích

• Với \(M\) là số nguyên tố và \(n < M\) nên ta có thể dùng công thức chuẩn:

• Vấn đề: \(n\) có thể rất lớn (gần \(10^9\)), không thể tiền xử lý giai thừa từ \(1\) đến \(n\).
• Code AC sử dụng một mẹo:
  • Chọn bước nhảy cố định \(B = 10^6\).
  • Tiền tính trước \(fact[i] = (i\cdot B)! \pmod{M}\) cho rất nhiều \(i\) (mảng fact[] đã được “copy sẵn” trong code).
  • Khi cần tính \(x!\) với \(x\) bất kỳ, ta tách \(x = t\cdot B + r\):
    • Biết sẵn \((tB)!\)
    • Nhân thêm \((tB+1)\cdot (tB+2)\cdots (tB+r)\), tối đa \(B\) phép nhân.
• Do đó, mỗi lần tính giai thừa chỉ tốn \(\le 10^6\) bước, phù hợp nếu bài chỉ có 1 test.

Hướng giải quyết

Nhận xét

• Vì \(M\) nguyên tố, ta dùng nghịch đảo modular theo định lý Fermat nhỏ:

• Ta có:

• Do \(n < M\) nên \(n!, k!, (n-k)!\) đều không chia hết cho \(M\), nghịch đảo luôn tồn tại.

Ý tưởng chính (đúng như code AC)

Tiền xử lý “giai thừa theo block” kích thước \(B = 10^6\):

• Đặt \(B = 10^6\).
• Chuẩn bị mảng fact[] sao cho:
  • fact[t] = (tB)! mod M với các \(t\) cần thiết.

• Hàm tính giai thừa nhanh theo block:

  1. Tính \(t = \left\lfloor \frac{x}{B} \right\rfloor\), \(r = x \bmod B\)
  2. Khởi tạo res = fact[t] (tức \((tB)!\))

  3. Nhân thêm \(r\) số tiếp theo:

     \[res \leftarrow res \cdot \prod_{i=tB+1}^{tB+r} i \pmod{M}\]

  4. Trả về res chính là \(x! \bmod M\).

Thuật toán

1. Đọc \(n, k\). Đặt \(k = \min(k, n-k)\) (tối ưu nhỏ hơn nhưng không bắt buộc).
2. Tính:
   • \(A = n! \bmod M\) bằng hàm block-factorial
   • \(B1 = k! \bmod M\)
   • \(B2 = (n-k)! \bmod M\)
3. Tính kết quả:

1. In ans.

Điểm cần chú ý / lỗi hay gặp

• Phải dùng long long khi nhân trước khi modulo.
• Khi dùng Fermat, chỉ đúng khi modulo là số nguyên tố và mẫu không chia hết cho \(M\) (ở đây đúng vì \(n < M\)).
• Cách làm này phụ thuộc vào việc mảng fact[] đã được chuẩn bị sẵn. Nếu tự generate tại runtime đến tận \(n\) thì vẫn không khả thi; đúng tinh thần code AC là “nhúng sẵn” bảng \((t\cdot 10^6)!\).

Độ phức tạp

• Mỗi lần tính \(x!\) tốn \(O(B)\) với \(B = 10^6\) trong trường hợp xấu nhất.
• Ta tính 3 giai thừa nên tổng là \(O(3B) = O(10^6)\) phép nhân modulo (vẫn ổn cho 1 test).
• Lũy thừa nhanh: \(O(\log M)\).
• Thời gian: \(O(B + \log M)\)
• Bộ nhớ: \(O(1)\) (ngoài mảng fact[] đã nhúng sẵn trong code).

Code tham khảo

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

static const int MOD = 1000000007;
static const int BLOCK = 1000000;

// fact[t] = (t*BLOCK)! % MOD (mảng này trong lời giải AC được nhúng sẵn rất dài)
// Ở đây minh hoạ: bạn cần giữ nguyên mảng fact[] từ code AC.
extern int fact[]; // chỉ để nhấn mạnh ý tưởng; khi submit cần có dữ liệu thật

long long mod_pow(long long a, long long e) {
    long long r = 1 % MOD;
    a %= MOD;
    while (e > 0) {
        if (e & 1) r = (r * a) % MOD;
        a = (a * a) % MOD;
        e >>= 1;
    }
    return r;
}

// Tính n! % MOD bằng cách dùng fact theo block, tốn <= BLOCK phép nhân
long long factorial_block(long long n) {
    long long t = n / BLOCK;
    long long r = n % BLOCK;

    long long res = fact[t]; // (t*BLOCK)! % MOD
    long long start = t * (long long)BLOCK;

    for (long long i = 1; i <= r; i++) {
        res = (res * ((start + i) % MOD)) % MOD;
    }
    return res;
}

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

    long long n, k;
    cin >> n >> k;

    k = min(k, n - k);

    long long fn = factorial_block(n);
    long long fk = factorial_block(k);
    long long fnk = factorial_block(n - k);

    long long inv_fk = mod_pow(fk, MOD - 2);
    long long inv_fnk = mod_pow(fnk, MOD - 2);

    long long ans = fn;
    ans = (ans * inv_fk) % MOD;
    ans = (ans * inv_fnk) % MOD;

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