Thi đấu

Tổ Hợp và Nghịch Đảo Modulo Trong Lập Trình Thi Đấu

Tính tổ hợp n chọn k theo modulo nguyên tố lớn bằng kỹ thuật tiền xử lý mảng giai thừa và nghịch đảo modulo qua định lý Fermat nhỏ trong độ phức tạp truy vấn O(1).

Tổ Hợp và Nghịch Đảo Modulo Trong Lập Trình Thi Đấu

Các bài toán đếm tổ hợp là một phần không thể thiếu trong các kỳ thi Học sinh giỏi Tin học và lập trình thi đấu. Để tránh hiện tượng số học quá lớn vượt khỏi phạm vi lưu trữ của kiểu dữ liệu 64-bit, hầu hết các đề thi đều yêu cầu in ra đáp án sau khi chia lấy dư cho một số nguyên tố lớn, phổ biến nhất là \(P = 10^9 + 7\) hoặc \(P = 998244353\).

Công thức tính số tổ hợp chập \(K\) của \(N\) phần tử được định nghĩa quen thuộc:

\[C(N, K) = \frac{N!}{K! \cdot (N - K)!}\]

Trong số học thông thường, phép chia phân số diễn ra dễ dàng. Tuy nhiên, trong số học đồng dư (Modular Arithmetic), phép chia không tồn tại trực tiếp. Biểu thức \((A / B) \pmod P\) hoàn toàn không bằng \((A \pmod P) / (B \pmod P)\). Để thực hiện phép chia dưới phép toán modulo, chúng ta bắt buộc phải chuyển đổi phép chia thành phép nhân với phần tử nghịch đảo modulo (Modular Multiplicative Inverse).

Bài viết này sẽ hướng dẫn bạn toàn bộ cơ sở toán học, chứng minh định lý Fermat nhỏ, kỹ thuật tính nghịch đảo bằng lũy thừa nhị phân và phương pháp tiền xử lý mảng giai thừa trong \(O(N)\) để trả lời mọi truy vấn tổ hợp chỉ trong thời gian \(O(1)\).

1. Bản chất của nghịch đảo modulo và Định lý Fermat nhỏ

Trong vành số học nguyên modulo \(P\), nghịch đảo modulo của một số nguyên \(A\) (kí hiệu là \(A^{-1}\)) là số nguyên \(X\) thỏa mãn phương trình đồng dư:

\[A \cdot X \equiv 1 \pmod P\]

Khi tìm được \(X\), phép chia \((A / B) \pmod P\) sẽ được chuyển thành:

\[\frac{A}{B} \equiv A \cdot B^{-1} \pmod P\]

Nghịch đảo modulo của \(A\) tồn tại khi và chỉ khi \(A\) và \(P\) nguyên tố cùng nhau, tức \(\gcd(A, P) = 1\).

Tính Tổ Hợp C(N, K) Modulo 10^9+7 & Nghịch Đảo Fermat Nhỏ Tiền xử lý giai thừa O(N) -> Truy vấn C(N, K) trong O(1) bằng invFact[K] * invFact[N - K] Công thức Nghịch đảo Modulo (Fermat) Khi P = 10^9 + 7 là số nguyên tố: a^(P - 1) ≡ 1 (mod P) => a^-1 ≡ a^(P - 2) (mod P) Tính nhanh bằng lũy thừa nhị phân O(log P) Kết quả C(10, 3) mod 10^9+7: 10! / (3! * 7!) = 120 (Chính xác!) Chạy tay tiền xử lý mảng invFact (N = 10^6) 1. fact[i] = fact[i - 1] * i % MOD 2. invFact[N] = power(fact[N], MOD - 2) 3. invFact[i - 1] = invFact[i] * i % MOD (Nhanh!) Truy vấn C(N, K) O(1): ans = fact[N] * invFact[K] % MOD ans = ans * invFact[N - K] % MOD
Tổ Hợp & Nghịch Đảo Modulo Tính C(N, K) mod 10^9+7 trong O(1) Định lý Fermat nhỏ: • a^-1 ≡ a^(MOD - 2) (mod MOD) • Tiền xử lý fact[N] mất O(N) • invFact[i-1] = invFact[i] * i % MOD Ví dụ chạy tay N = 10, K = 3: fact[10] = 3628800 invFact[3] * invFact[7] = 1/30240 => C(10, 3) = 120 (chính xác) Truy vấn mỗi câu hỏi chỉ tốn O(1)
Quy trình tiền xử lý mảng giai thừa và nghịch đảo giai thừa giúp tính tổ hợp C(N, K) trong O(1).

Định lý Fermat nhỏ (Fermat's Little Theorem)

Định lý Fermat nhỏ phát biểu rằng: Nếu \(P\) là một số nguyên tố và \(A\) là một số nguyên không chia hết cho \(P\), thì:

\[A^{P - 1} \equiv 1 \pmod P\]

Nhân cả hai vế với \(A^{-1}\), ta suy ra ngay hệ quả kỳ diệu:

\[A^{P - 2} \equiv A^{-1} \pmod P\]

Như vậy, để tìm nghịch đảo modulo của \(A\) theo modulo nguyên tố \(P\), ta chỉ cần tính lũy thừa \(A^{P - 2} \pmod P\). Nhờ thuật toán lũy thừa nhị phân (Binary Exponentiation), phép tính này chỉ tiêu tốn đúng \(O(\log P)\) phép toán!

2. Kỹ thuật tiền xử lý giai thừa và nghịch đảo giai thừa trong O(N)

Trong các bài toán thi đấu thực tế, số lượng truy vấn \(Q\) có thể lên tới \(10^5\) hoặc \(10^6\) với \(N, K \le 10^6\). Nếu với mỗi truy vấn bạn lại gọi hàm lũy thừa nhị phân để tính nghịch đảo của \(K!\) và \((N - K)!\), độ phức tạp tổng cộng sẽ là \(O(Q \log P)\), rất dễ chạm ngưỡng TLE khi thời gian thi đấu chỉ có 1 giây.

Để tối ưu hóa thời gian trả lời xuống \(O(1)\), chúng ta sử dụng kỹ thuật tiền xử lý hai mảng:

  1. Mảng fact[i]: lưu giá trị \(i! \pmod P\).
  2. Mảng invFact[i]: lưu giá trị \((i!)^{-1} \pmod P\).

Bước 1: Tính mảng giai thừa xuôi

\[fact[i] = (fact[i - 1] \times i) \pmod P\] Khởi tạo \(fact[0] = 1\). Quá trình này hoàn thành trong \(O(N)\) phép nhân.

Bước 2: Tính nghịch đảo của giai thừa lớn nhất

Chúng ta chỉ cần gọi hàm lũy thừa nhị phân đúng 1 lần duy nhất cho phần tử cuối cùng của mảng: \[invFact[N] = (fact[N])^{P - 2} \pmod P\]

Bước 3: Lần ngược mảng nghịch đảo trong O(N)

Dựa vào đẳng thức toán học: \[\frac{1}{(i - 1)!} = \frac{1}{i!} \times i\] Chúng ta dễ dàng suy ra công thức truy hồi ngược cho nghịch đảo giai thừa: \[invFact[i - 1] = (invFact[i] \times i) \pmod P\]

Chỉ với một vòng lặp chạy ngược từ \(N - 1\) về \(0\), toàn bộ mảng invFact được điền đầy đủ mà không cần thực hiện thêm bất kỳ phép lũy thừa nhị phân nào!

Bước 4: Trả lời truy vấn trong O(1)

Với mọi cặp số \((N, K)\), công thức tính tổ hợp trở thành: \[C(N, K) = fact[N] \times invFact[K] \times invFact[N - K] \pmod P\]

Học cùng giảng viên

Chủ đề này nằm trong Buổi 10 - Modular Inverse & Combinatorics của Tài năng lập trình. Xem đề cương

3. Cài đặt chuẩn C++17 và Python 3

Dưới đây là mã nguồn chuẩn tối ưu dành cho môi trường thi đấu:

Cài đặt C++17

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 1000000;

long long fact[MAXN + 1];
long long invFact[MAXN + 1];

// Luy thua nhi phan tinh base^exp mod MOD trong O(log exp)
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// Tinh nghich dao modulo bang dinh ly Fermat nho
long long modInverse(long long n) {
    return power(n, MOD - 2);
}

// Tien xu ly giai thua va nghich dao giai thua trong O(MAXN)
void precompute() {
    fact[0] = 1;
    invFact[0] = 1;
    for (int i = 1; i <= MAXN; ++i) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }
    // Chi goi power 1 lan duy nhat cho MAXN
    invFact[MAXN] = modInverse(fact[MAXN]);
    for (int i = MAXN - 1; i >= 1; --i) {
        invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
    }
}

// Tinh to hop C(n, r) trong O(1)
long long nCr(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fact[n] * invFact[r] % MOD * invFact[n - r] % MOD;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    precompute();
    
    // Test case nho: C(10, 3) = 120
    cout << nCr(10, 3) << '\n';
    // Test case lon: C(1000, 500) mod 10^9+7
    cout << nCr(1000, 500) << '\n';
    
    return 0;
}

Cài đặt Python 3

import sys

MOD = 10**9 + 7
MAXN = 1000000

fact = [1] * (MAXN + 1)
invFact = [1] * (MAXN + 1)

def power(base: int, exp: int) -> int:
    res = 1
    base %= MOD
    while exp > 0:
        if exp % 2 == 1:
            res = (res * base) % MOD
        base = (base * base) % MOD
        exp //= 2
    return res

def precompute():
    for i in range(1, MAXN + 1):
        fact[i] = (fact[i - 1] * i) % MOD
    invFact[MAXN] = power(fact[MAXN], MOD - 2)
    for i in range(MAXN - 1, 0, -1):
        invFact[i] = (invFact[i + 1] * (i + 1)) % MOD

def nCr(n: int, r: int) -> int:
    if r < 0 or r > n:
        return 0
    return fact[n] * invFact[r] % MOD * invFact[n - r] % MOD

def main():
    precompute()
    print(nCr(10, 3))
    print(nCr(1000, 500))

if __name__ == '__main__':
    main()

4. Các ứng dụng kinh điển của tổ hợp trong lập trình thi đấu

Kỹ thuật tính tổ hợp \(O(1)\) là viên gạch nền tảng để giải quyết hàng loạt bài toán đếm nâng cao:

  1. Bài toán chia kẹo Euler (Stars and Bars): Số cách chia \(N\) chiếc kẹo giống nhau cho \(K\) đứa trẻ sao cho mỗi đứa có ít nhất 1 chiếc kẹo chính là số cách đặt \(K - 1\) vách ngăn vào \(N - 1\) khoảng trống: \[\text{Số cách} = C(N - 1, K - 1)\] Nếu cho phép trẻ có 0 chiếc kẹo: \[\text{Số cách} = C(N + K - 1, K - 1)\]
  2. Số Catalan: Số dãy ngoặc đúng độ dài \(2N\), số cây nhị phân có \(N\) nút hoặc số cách tam giác hóa đa giác lồi \(N+2\) đỉnh đều tuân theo công thức số Catalan: \[C_n = \frac{1}{n + 1} C(2n, n) = (C(2n, n) - C(2n, n - 1)) \pmod P\]
  3. Đếm đường đi trên lưới: Số đường đi ngắn nhất từ tọa độ \((0, 0)\) đến \((X, Y)\) trên lưới nguyên chỉ bằng các bước đi sang phải hoặc đi lên trên là: \[\text{Số đường} = C(X + Y, X)\]

So sánh các phương pháp tính tổ hợp trong thi đấu

Tùy thuộc vào giới hạn của \(N, K, Q\) và modulo \(P\), người làm bài cần chọn phương pháp phù hợp nhất:

Phương pháp Tiền xử lý Mỗi truy vấn Giới hạn tối ưu Điều kiện áp dụng
Tam giác Pascal \(O(N^2)\) \(O(1)\) \(N, K \le 2000\) Modulo \(P\) bất kỳ (kể cả hợp số)
Lũy thừa Fermat trực tiếp \(O(1)\) \(O(K \log P)\) \(K \le 10^5, Q \le 10\) \(P\) nguyên tố, số truy vấn rất ít
Mảng giai thừa nghịch đảo \(O(N)\) \(O(1)\) \(N, K \le 10^6, Q \le 10^6\) \(P\) nguyên tố lớn (\(10^9+7\))
Định lý Lucas \(O(P)\) \(O(\log_P N)\) \(N \le 10^{18}, P \le 10^5\) \(P\) nguyên tố nhỏ

Chạy tay từng bước tính nghịch đảo mảng giai thừa

Để hiểu rõ tại sao vòng lặp chạy ngược lại điền đúng mảng nghịch đảo giai thừa, xét ví dụ nhỏ với \(N = 5\) và số nguyên tố \(P = 7\):

  1. Khởi tạo mảng giai thừa xuôi:

    • \(fact[0] = 1\)
    • \(fact[1] = (1 \times 1) \pmod 7 = 1\)
    • \(fact[2] = (1 \times 2) \pmod 7 = 2\)
    • \(fact[3] = (2 \times 3) \pmod 7 = 6\)
    • \(fact[4] = (6 \times 4) \pmod 7 = 24 \equiv 3\)
    • \(fact[5] = (3 \times 5) \pmod 7 = 15 \equiv 1\)
  2. Tính nghịch đảo phần tử cuối cùng bằng lũy thừa nhị phân:

    • \(invFact[5] = fact[5]^{7 - 2} \pmod 7 = 1^5 \pmod 7 = 1\)
  3. Lần ngược mảng nghịch đảo giai thừa:

    • \(invFact[4] = (invFact[5] \times 5) \pmod 7 = (1 \times 5) \pmod 7 = 5\). Kiểm tra: \(fact[4] \times invFact[4] = 3 \times 5 = 15 \equiv 1\) (Chính xác!).
    • \(invFact[3] = (invFact[4] \times 4) \pmod 7 = (5 \times 4) \pmod 7 = 20 \equiv 6\). Kiểm tra: \(fact[3] \times invFact[3] = 6 \times 6 = 36 \equiv 1\) (Chính xác!).
    • \(invFact[2] = (invFact[3] \times 3) \pmod 7 = (6 \times 3) \pmod 7 = 18 \equiv 4\). Kiểm tra: \(fact[2] \times invFact[2] = 2 \times 4 = 8 \equiv 1\) (Chính xác!).
    • \(invFact[1] = (invFact[2] \times 2) \pmod 7 = (4 \times 2) \pmod 7 = 8 \equiv 1\). Kiểm tra: \(fact[1] \times invFact[1] = 1 \times 1 = 1\) (Chính xác!).
    • \(invFact[0] = (invFact[1] \times 1) \pmod 7 = 1\).

Nhờ quan hệ đại số giữa giai thừa của hai số liên tiếp, toàn bộ mảng được điền chính xác tuyệt đối mà không cần tính lại nghịch đảo từng số.

Bốn bẫy sai lầm kinh điển trong phòng thi

Khi lập trình các bài toán tổ hợp và số học đồng dư, thí sinh thường mắc phải các lỗi cơ bản sau:

  1. Quên ép kiểu 64-bit trước khi nhân: Trong C++, kiểu int chỉ chứa được giá trị tới xấp xỉ \(2 \times 10^9\). Khi nhân hai số \(A, B \approx 10^9\), tích số sẽ đạt \(10^{18}\), gây tràn số kiểu int ngay lập tức trước khi phép chia modulo được thực hiện. Luôn viết 1LL * fact[n] * invFact[k] % MOD hoặc khai báo mảng kiểu long long.

  2. Bỏ qua điều kiện biên của tổ hợp: Hàm tính tổ hợp cần kiểm tra ngay điều kiện \(k < 0\) hoặc \(k > n\) để trả về 0. Nếu truy cập trực tiếp invFact[n - k] khi \(k > n\), chỉ số âm sẽ gây lỗi bộ nhớ nghiêm trọng (RTE) hoặc đọc giá trị rác.

  3. Sai lầm khi thực hiện phép trừ theo modulo: Trong các công thức như số Catalan \(C_n = C(2n, n) - C(2n, n - 1)\), kết quả phép trừ có thể mang giá trị âm. Luôn áp dụng công thức an toàn: (val1 - val2 + MOD) % MOD.

  4. Áp dụng sai định lý khi modulo không phải số nguyên tố: Định lý Fermat nhỏ chỉ áp dụng khi modulo là số nguyên tố. Nếu đề bài cho modulo là hợp số, việc tính lũy thừa \(A^{M - 2}\) sẽ cho kết quả sai hoàn toàn. Lúc này, bạn cần chuyển sang thuật toán Euclid mở rộng hoặc phân tích thừa số nguyên tố.

Luyện ngay trên Big-O Coding

Để thực hành thành thạo kỹ thuật tính tổ hợp và đồng dư modulo, bạn hãy giải ngay các bài tập sau trên hệ thống Big-O Coding:

Nếu Modulo không phải là số nguyên tố thì có dùng được định lý Fermat nhỏ không?

Không. Định lý Fermat nhỏ chỉ đúng khi modulo \(P\) là số nguyên tố. Nếu modulo \(M\) là hợp số nhưng \(\gcd(A, M) = 1\), bạn phải áp dụng Định lý Euler \(A^{\phi(M)} \equiv 1 \pmod M\), hoặc sử dụng thuật toán Euclid mở rộng (Extended Euclidean Algorithm) để tìm nghiệm phương trình \(A \cdot X + M \cdot Y = 1\).

Tại sao khi nhân ba số trong C++ phải chia modulo hai lần?

Phép nhân hai số nguyên \(10^9\) có thể đạt \(10^{18}\), vừa vặn nằm trong giới hạn của kiểu long long. Nếu bạn viết (a * b * c) % MOD, kết quả của (a * b) khi nhân tiếp với c sẽ đạt tới \(10^{27}\), gây tràn số long long nghiêm trọng. Do đó, quy tắc bất di bất dịch là luôn lấy modulo sau mỗi lần nhân: (1LL * a * b % MOD) * c % MOD.

Nguồn tham khảo

Muốn học bài bản cùng giảng viên?

Lộ trình 4 cấp độ cho học sinh thi Tin học trẻ, Chuyên Tin, Olympic, ACM-ICPC: xếp lớp theo năng lực, mini contest, lớp Đội tuyển. Học online, phí theo tháng.

Xem Tài năng lập trình

Nguồn tham khảo

Chia sẻ: Facebook LinkedIn
Nhắn Zalo tư vấnZalo Gọi 0937 401 483