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\).
Đị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:
- Mảng
fact[i]: lưu giá trị \(i! \pmod P\). - 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\]
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:
- 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)\]
- 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\]
- Đế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\):
-
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\)
-
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\)
-
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:
-
Quên ép kiểu 64-bit trước khi nhân: Trong C++, kiểu
intchỉ 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ểuintngay lập tức trước khi phép chia modulo được thực hiện. Luôn viết1LL * fact[n] * invFact[k] % MODhoặc khai báo mảng kiểulong long. -
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. -
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. -
Á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
- CP-Algorithms - Modular Multiplicative Inverse - Lý thuyết toàn diện về các phương pháp tính nghịch đảo modulo
- VNOI Wiki - Nghịch đảo modulo - Tài liệu giảng dạy chuyên đề số học của cộng đồng VNOI
- USACO Guide - Combinatorics - Bài tập và chiến thuật làm bài tổ hợp của đội tuyển Olympic Mỹ
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.


