Bài 26: Toán modulo và tổ hợp trong C++ và Python: lũy thừa nhanh, nghịch đảo modulo, tính tổ hợp C(n, k) mod p
Lời mở đầu
Ở bài 12 (số học cơ bản) em đã làm quen với phép chia lấy dư, ước chung lớn nhất và thuật toán Euclid. Ở bài 19 (quy hoạch động) em đã gặp những bài đếm số cách mà đáp án lớn tới mức đề bắt “in kết quả theo modulo $10^9 + 7$”. Hôm nay ta gom tất cả lại thành một bộ công cụ hoàn chỉnh, thứ mà gần như đề HSG nào có bài đếm cũng cần tới.
Bài học đi theo một mạch rất tự nhiên: hiểu luật chơi của phép tính modulo (cộng, trừ, nhân được, còn chia thì không), rồi học lũy thừa nhanh (đã gặp ở bài tập 2 của bài 24 chia để trị), dùng lũy thừa nhanh để tìm nghịch đảo modulo, tức là “chia” được trong modulo. Cuối cùng là phần thưởng: tính tổ hợp $C(n, k)$ thật nhanh và giải hàng loạt bài đếm kinh điển như chia kẹo, đếm đường đi trên lưới.
Lộ trình bài viết, bấm vào từng phần để nhảy tới:
Phần 1Phép tính modulo: cộng, trừ, nhân
Vì sao đề bắt lấy dư? Số cách xếp 20 bạn thành hàng là $20! \approx 2{,}4 \cdot 10^{18}$, vừa chạm giới hạn của long long. Với $100!$ (khoảng 158 chữ số) thì không kiểu số nguyên nào chứa nổi. Để bài vẫn chấm được bằng số nguyên bình thường, người ra đề chỉ yêu cầu in số dư của đáp án khi chia cho một số $m$ cố định, thường là $m = 10^9 + 7$ (hoặc $998\,244\,353$).
Vì sao lại là $10^9 + 7$? Ba lý do: nó là số nguyên tố (ở phần 3 em sẽ thấy điều này giúp ta “chia” được); nó nhỏ hơn $2^{30}$ nên tổng hai số dư vẫn vừa kiểu int; và tích hai số dư nhỏ hơn $(10^9 + 7)^2 \approx 10^{18}$, vẫn vừa long long (giới hạn khoảng $9{,}2 \cdot 10^{18}$).
Ta viết $a \equiv b \pmod m$ (đọc là “$a$ đồng dư với $b$ theo modulo $m$”) nếu $a$ và $b$ có cùng số dư khi chia cho $m$, tức là $m$ chia hết $a - b$. Hãy hình dung các số dư xếp thành một vòng tròn như mặt đồng hồ: đi quá $m - 1$ thì quay về $0$.
Hình 1. Modulo 7 như một chiếc đồng hồ có 7 vạch: đứng ở 5, đi thêm 4 bước thì dừng ở 2. Vậy $5 + 4 = 9 \equiv 2 \pmod 7$.
Điều tuyệt vời của modulo là ta được phép lấy dư ở bất kỳ bước trung gian nào của phép cộng, trừ, nhân mà kết quả cuối cùng không đổi. Nhờ vậy các số luôn được giữ nhỏ hơn $m$, không bao giờ phình to:
| Phép tính | Quy tắc | Ví dụ với $m = 7$ |
|---|---|---|
| Cộng | $(a + b) \bmod m = \big((a \bmod m) + (b \bmod m)\big) \bmod m$ | $(12 + 20) \bmod 7 = (5 + 6) \bmod 7 = 4$ |
| Trừ | $(a - b) \bmod m = \big((a \bmod m) - (b \bmod m) + m\big) \bmod m$ | $(15 - 20) \bmod 7 = (1 - 6 + 7) \bmod 7 = 2$ |
| Nhân | $(a \cdot b) \bmod m = \big((a \bmod m) \cdot (b \bmod m)\big) \bmod m$ | $(12 \cdot 20) \bmod 7 = (5 \cdot 6) \bmod 7 = 2$ |
| Chia | KHÔNG làm như trên được | $(12 / 4) \bmod 7 = 3$, nhưng $12 \bmod 7 = 5$ không chia hết cho 4 |
Bảng 1. Ba phép cộng, trừ, nhân “đi xuyên” qua phép lấy dư. Riêng phép chia phải đợi tới phần 3 (nghịch đảo modulo).
% giữ dấu của số bị chia: -5 % 7 cho −5 chứ không phải 2. Vì vậy sau khi trừ, em phải cộng thêm MOD: (a - b + MOD) % MOD (đúng khi $a, b$ đã nằm trong $[0, m)$). Nếu một số đọc vào có thể âm bất kỳ, dùng ((x % MOD) + MOD) % MOD. Python thì khác: -5 % 7 cho 2, kết quả luôn cùng dấu với số chia, nên không phải lo.int thì tràn ngay. Quy tắc an toàn: mọi biến lưu số dư khai báo long long, và lấy dư sau mỗi phép nhân: a * b % MOD * c % MOD, đừng viết a * b * c % MOD (tích ba số cỡ $10^{27}$ đã tràn trước khi kịp lấy dư). Nếu $m$ lớn tới $10^{18}$ thì tích hai số dư lên tới $10^{36}$, vượt cả long long. Khi đó dùng kiểu __int128 của GCC: (__int128)a * b % m (có ở bài tập 1).Chương trình nhỏ dưới đây áp dụng cả ba quy tắc: đọc $n$ số nguyên (có thể âm, tới $10^{18}$), in tổng $S$, tích $P$ và hiệu $S - P$, tất cả theo modulo $10^9 + 7$. Với dữ liệu mẫu, hai số $-1$ và $10^9 + 6$ là cùng một số dư; tổng thật bằng $10^9 + 10$, tích thật bằng $-5 \cdot 10^9 - 30$, nhưng ta không cần tính ra số thật.
Xem code C++ / Python: cộng, trừ, nhân trong modulo, xử lý số âm (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
int main(){
int n;
cin >> n;
long long S = 0, P = 1;
for(int i = 0; i < n; i++){
long long x;
cin >> x;
x %= MOD; // x nằm trong (-MOD, MOD), có thể âm
if(x < 0) x += MOD; // đưa về [0, MOD)
S = (S + x) % MOD; // cộng xong lấy dư ngay
P = P * x % MOD; // hai số < MOD: tích < 10^18, vừa long long
}
long long D = (S - P + MOD) % MOD; // trừ xong cộng MOD để không bị âm
cout << S << "\n" << P << "\n" << D;
return 0;
}import sys
MOD = 10**9 + 7
data = sys.stdin.read().split()
n = int(data[0])
S, P = 0, 1
for t in data[1:n + 1]:
x = int(t) % MOD # Python: kết quả % luôn không âm
S = (S + x) % MOD
P = P * x % MOD
D = (S - P) % MOD # vẫn không âm, không cần cộng MOD
print(S, P, D, sep='\n')Phần 2Lũy thừa nhanh $O(\log b)$
Bài toán: tính $a^b \bmod m$ với $b$ có thể tới $10^{18}$. Nhân $a$ lần lượt $b$ lần là $10^{18}$ phép nhân, chạy tới cả nghìn năm. Ở bài tập 2 của bài 24 em đã gặp cách chia để trị: $a^b = (a^{b/2})^2$, nhân thêm $a$ nếu $b$ lẻ. Hôm nay ta viết lại cách đó bằng vòng lặp, ngắn hơn, không đệ quy, và dễ hiểu qua hệ nhị phân (bài 20 thao tác bit).
Ý tưởng: viết $b$ dưới dạng nhị phân. Ví dụ $13 = 1101_2 = 8 + 4 + 1$, nên
$3^{13} = 3^{8} \cdot 3^{4} \cdot 3^{1}$.
Các lũy thừa $a^1, a^2, a^4, a^8, \ldots$ tính được rất rẻ: mỗi số là bình phương của số trước. Ta duyệt các bit của $b$ từ thấp lên cao, giữ biến a lần lượt bằng $a^{2^0}, a^{2^1}, a^{2^2}, \ldots$; gặp bit 1 thì nhân a hiện tại vào kết quả res. Số bit của $b$ là khoảng $\log_2 b$, nên với $b = 10^{18}$ chỉ cần khoảng 60 vòng lặp, mỗi vòng tối đa 2 phép nhân.
| Bit thứ i | Bit của 13 | a = $3^{2^i}$ | Nhân vào res? | res |
|---|---|---|---|---|
| 0 | 1 | $3^1 = 3$ | ✔ có | 3 |
| 1 | 0 | $3^2 = 9$ | ✘ không | 3 |
| 2 | 1 | $3^4 = 81$ | ✔ có | $3 \cdot 81 = 243$ |
| 3 | 1 | $3^8 = 6561$ | ✔ có | $243 \cdot 6561 = 1\,594\,323$ |
Bảng 2. Tính $3^{13}$: chỉ 4 vòng lặp (13 có 4 bit) thay vì 12 phép nhân. Kết quả $1\,594\,323 = 3^{13}$, nhỏ hơn $10^9 + 7$ nên lấy dư không đổi.
Xem code C++ / Python: lũy thừa nhanh bằng vòng lặp (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
long long power(long long a, long long b, long long m){
long long res = 1 % m; // m = 1 thì mọi số đều ≡ 0
a %= m;
while(b > 0){
if(b & 1) res = res * a % m; // bit thấp nhất của b là 1
a = a * a % m; // a, a^2, a^4, a^8, ...
b >>= 1; // bỏ bit thấp nhất
}
return res;
}
int main(){
long long a, b, m;
cin >> a >> b >> m;
cout << power(a, b, m);
return 0;
}def power(a, b, m):
res = 1 % m
a %= m
while b > 0:
if b & 1: # bit thấp nhất của b là 1
res = res * a % m
a = a * a % m # a, a^2, a^4, a^8, ...
b >>= 1 # bỏ bit thấp nhất
return res
a, b, m = map(int, input().split())
print(power(a, b, m)) # Python có sẵn: pow(a, b, m)Em chạy tay từng dòng để thấy biến b “mất dần” bit thấp nhất sau mỗi vòng, còn a thì bình phương liên tục. Thử thêm dữ liệu “b = 0” và “m = 1” để kiểm tra hai trường hợp biên:
long long power(long long a, long long b, long long m){
long long res = 1 % m;
a %= m;
while(b > 0){
if(b & 1) res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}a %= m (nếu $a$ đọc vào cỡ $10^{18}$ thì a * a tràn ngay vòng đầu); viết res = 1 khi $m = 1$ (phải in 0); và dùng int cho a, res. Trong Python chỉ cần gọi hàm có sẵn pow(a, b, m), nó cũng chạy đúng thuật toán này.Phần 3Nghịch đảo modulo: “chia” trong modulo
Trong số thực, chia cho $b$ chính là nhân với $\frac{1}{b}$, số mà $b \cdot \frac{1}{b} = 1$. Trong modulo ta làm y như vậy: nghịch đảo của $b$ theo modulo $m$ là số $x$ trong $[0, m)$ sao cho
$b \cdot x \equiv 1 \pmod m$, ta viết $x = b^{-1} \bmod m$.
Khi đó “$a / b$” theo modulo $m$ được hiểu là $a \cdot b^{-1} \bmod m$. Ví dụ với $m = 7$: $3 \cdot 5 = 15 \equiv 1$, nên $3^{-1} \equiv 5 \pmod 7$. Kiểm tra: $12 / 4 = 3$; theo modulo 7 thì $12 \equiv 5$, $4^{-1} \equiv 2$ (vì $4 \cdot 2 = 8 \equiv 1$), và $5 \cdot 2 = 10 \equiv 3$. Khớp!
Khi nào có nghịch đảo? $b$ có nghịch đảo modulo $m$ khi và chỉ khi $\gcd(b, m) = 1$. Chẳng hạn $2$ không có nghịch đảo modulo $4$: $2x$ luôn chẵn, chia 4 chỉ dư 0 hoặc 2, không bao giờ dư 1. Khi $m$ là số nguyên tố $p$ thì mọi $b$ không chia hết cho $p$ đều có nghịch đảo. Đây là lý do lớn nhất để đề chọn $10^9 + 7$.
Cách 1: định lý Fermat nhỏ (khi $p$ nguyên tố)
Định lý Fermat nhỏ: nếu $p$ là số nguyên tố và $a$ không chia hết cho $p$ thì $a^{p-1} \equiv 1 \pmod p$. Tách $a^{p-1} = a \cdot a^{p-2}$, ta được ngay $a \cdot a^{p-2} \equiv 1$, nghĩa là
$a^{-1} \equiv a^{p-2} \pmod p$.
Vậy nghịch đảo chỉ là một lần gọi lũy thừa nhanh với số mũ $p - 2$, tốn $O(\log p)$, khoảng 30 vòng lặp với $p = 10^9 + 7$. Thử với $p = 7$, $a = 3$: $3^{5} = 243 = 34 \cdot 7 + 5$, đúng là $3^{-1} \equiv 5$. Với $p = 10^9 + 7$: $2^{-1} \equiv 500\,000\,004$ (vì $2 \cdot 500\,000\,004 = 10^9 + 8 \equiv 1$).
Xem code C++ / Python: nghịch đảo modulo số nguyên tố bằng định lý Fermat nhỏ (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
long long power(long long a, long long b, long long m){
long long res = 1 % m;
a %= m;
while(b > 0){
if(b & 1) res = res * a % m;
a = a * a % m;
b >>= 1;
}
return res;
}
int main(){
int T;
long long p; // p nguyên tố
cin >> T >> p;
while(T--){
long long a;
cin >> a; // a không chia hết cho p
cout << power(a, p - 2, p) << " "; // a^(p-2) là nghịch đảo của a
}
return 0;
}import sys
data = sys.stdin.read().split()
T, p = int(data[0]), int(data[1]) # p nguyên tố
res = [pow(int(x), p - 2, p) for x in data[2:2 + T]]
print(*res) # Python 3.8+: pow(a, -1, p) cũng đượcCách 2: Euclid mở rộng (khi $m$ bất kỳ)
Nếu $m$ không nguyên tố (ví dụ $m = 26$, $m = 10^9$), Fermat không dùng được. Ta quay lại thuật toán Euclid ở bài 12: $\gcd(a, b) = \gcd(b, a \bmod b)$. Thuật toán Euclid mở rộng không chỉ tìm $g = \gcd(a, b)$ mà còn tìm hai số nguyên $x, y$ sao cho
$a \cdot x + b \cdot y = g$.
Cách tìm: khi $b = 0$ thì $g = a$, chọn $x = 1, y = 0$. Ngược lại, gọi đệ quy cho $(b, a \bmod b)$ để có $x', y'$ với $b x' + (a \bmod b) y' = g$. Thay $a \bmod b = a - q b$ (với $q = \lfloor a / b \rfloor$) và gom lại: $a \cdot y' + b \cdot (x' - q y') = g$. Vậy
$x = y'$, $\quad y = x' - q \cdot y'$.
Áp dụng cho cặp $(a, m)$: nếu $g = 1$ thì $a x + m y = 1$, lấy modulo $m$ hai vế (số hạng $m y$ biến mất) được $a x \equiv 1$. Vậy $x$ (đưa về $[0, m)$) chính là nghịch đảo. Nếu $g \ne 1$ thì không có nghịch đảo. Em xem bảng “đi xuống” rồi “đi lên” trong mô phỏng với $a = 7$, $m = 26$:
Xem code C++ / Python: nghịch đảo modulo bằng Euclid mở rộng (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
// trả về g = gcd(a, b) và tìm x, y sao cho a*x + b*y = g
long long extgcd(long long a, long long b, long long &x, long long &y){
if(b == 0){ x = 1; y = 0; return a; }
long long x1, y1;
long long g = extgcd(b, a % b, x1, y1);
x = y1;
y = x1 - (a / b) * y1;
return g;
}
int main(){
long long a, m;
cin >> a >> m;
long long x, y;
long long g = extgcd(a % m, m, x, y);
if(g != 1) cout << -1; // không có nghịch đảo
else cout << (x % m + m) % m; // đưa x về [0, m)
return 0;
}def extgcd(a, b):
"""Trả về (g, x, y) với a*x + b*y = g = gcd(a, b)."""
if b == 0:
return a, 1, 0
g, x1, y1 = extgcd(b, a % b)
return g, y1, x1 - (a // b) * y1
a, m = map(int, input().split())
g, x, y = extgcd(a % m, m)
print(-1 if g != 1 else x % m) # x % m của Python luôn không âm| Fermat nhỏ | Euclid mở rộng | |
|---|---|---|
| Điều kiện | $m = p$ nguyên tố, $p \nmid a$ | $\gcd(a, m) = 1$, $m$ bất kỳ |
| Độ phức tạp | $O(\log p)$ | $O(\log m)$ |
| Cài đặt | một dòng power(a, p - 2, p) | hàm đệ quy ngắn |
| Dùng khi | $m = 10^9 + 7$, $998\,244\,353$ (gần như mọi bài) | $m$ không nguyên tố, hoặc cần giải $a x \equiv b \pmod m$ |
Bảng 3. Hai cách tìm nghịch đảo modulo.
A % p * power(B % p, p - 2, p) % p. Và nhớ: nếu $B$ chia hết cho $p$ thì $B \bmod p = 0$, không có nghịch đảo, công thức sai hoàn toàn.Phần 4Tổ hợp: tính $C(n, k)$ thật nhanh
Trước khi tính, ta ôn lại hai quy tắc đếm nền tảng:
- Quy tắc cộng: một việc làm theo cách A hoặc cách B (không trùng nhau), A có $x$ cách, B có $y$ cách thì có $x + y$ cách. Ví dụ đi từ nhà tới trường bằng 3 tuyến xe buýt hoặc 2 đường đi bộ: $3 + 2 = 5$ cách.
- Quy tắc nhân: một việc gồm bước 1 rồi bước 2, bước 1 có $x$ cách, mỗi cách đó bước 2 có $y$ cách thì có $x \cdot y$ cách. Ví dụ chọn 1 áo trong 4 áo và 1 quần trong 3 quần: $4 \cdot 3 = 12$ bộ.
Từ quy tắc nhân ta có ba khái niệm quen thuộc (với $n$ phần tử khác nhau):
| Khái niệm | Ý nghĩa | Công thức | Ví dụ $n = 5$, $k = 2$ |
|---|---|---|---|
| Hoán vị $P_n$ | xếp cả $n$ phần tử thành hàng | $n! = 1 \cdot 2 \cdots n$ | $5! = 120$ |
| Chỉnh hợp $A(n, k)$ | chọn $k$ phần tử có thứ tự | $\dfrac{n!}{(n-k)!}$ | $5 \cdot 4 = 20$ (chọn lớp trưởng, lớp phó) |
| Tổ hợp $C(n, k)$ | chọn $k$ phần tử không thứ tự | $\dfrac{n!}{k!\,(n-k)!}$ | $\frac{20}{2} = 10$ (chọn 2 bạn trực nhật) |
Bảng 4. Hoán vị, chỉnh hợp, tổ hợp. Chỉnh hợp chia cho $k!$ (số cách xếp thứ tự $k$ người đã chọn) thì ra tổ hợp. $C(n, k)$ còn được viết là $\binom{n}{k}$.
Vấn đề: công thức $C(n, k) = \frac{n!}{k!(n-k)!}$ có phép chia, còn $n!$ thì khổng lồ. Ta có hai cách tránh.
Cách 1: tam giác Pascal, chỉ dùng phép cộng
Xét phần tử cuối cùng trong $n$ phần tử. Khi chọn $k$ phần tử, hoặc ta chọn nó (còn phải chọn $k - 1$ trong $n - 1$ phần tử kia), hoặc không chọn nó (chọn đủ $k$ trong $n - 1$ phần tử kia). Theo quy tắc cộng:
$C(n, k) = C(n-1, k-1) + C(n-1, k)$, với $C(n, 0) = C(n, n) = 1$.
Đây đúng là một công thức quy hoạch động: điền bảng theo từng hàng, mỗi ô bằng tổng hai ô phía trên. Vì chỉ có phép cộng nên dùng được với mọi modulo $m$, kể cả không nguyên tố. Đổi lại, bảng có $O(n^2)$ ô: chỉ dùng được khi $n \le$ khoảng $5000$.
Xem code C++ / Python: bảng tam giác Pascal, modulo bất kỳ (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
int C[2001][2001];
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int Q;
long long m; // m bất kỳ, không cần nguyên tố
cin >> Q >> m;
for(int i = 0; i <= 2000; i++){
C[i][0] = C[i][i] = 1 % m;
for(int k = 1; k < i; k++)
C[i][k] = ((long long)C[i - 1][k - 1] + C[i - 1][k]) % m;
}
while(Q--){
int n, k;
cin >> n >> k;
cout << (k < 0 || k > n ? 0 : C[n][k]) << "\n";
}
return 0;
}import sys
data = sys.stdin.read().split()
Q, m = int(data[0]), int(data[1])
qs = [(int(data[2 + 2 * i]), int(data[3 + 2 * i])) for i in range(Q)]
N = max(n for n, k in qs)
C = [[1 % m]]
for i in range(1, N + 1):
prev = C[-1]
row = [1 % m] + [(prev[k - 1] + prev[k]) % m for k in range(1, i)] + [1 % m]
C.append(row)
out = [str(C[n][k]) if 0 <= k <= n else '0' for n, k in qs]
print('\n'.join(out))Cách 2: giai thừa và nghịch đảo giai thừa
Khi $n$ tới $10^6$ và modulo là số nguyên tố $p$ (lớn hơn $n$), ta tính trực tiếp công thức, thay phép chia bằng nhân nghịch đảo:
$C(n, k) = n! \cdot (k!)^{-1} \cdot ((n-k)!)^{-1} \bmod p$.
Chuẩn bị trước hai mảng: fact[i] $= i! \bmod p$ và inv[i] $= (i!)^{-1} \bmod p$. Mảng fact dễ: fact[i] = fact[i-1] * i. Mảng inv nếu gọi lũy thừa nhanh cho từng $i$ thì tốn $O(n \log p)$, vẫn ổn nhưng có mẹo hay hơn: chỉ tính một giá trị inv[N] bằng Fermat, rồi đi ngược
$\dfrac{1}{(i-1)!} = \dfrac{i}{i!}$, tức là inv[i-1] = inv[i] * i % p.
Tổng chi phí chuẩn bị là $O(N + \log p)$, sau đó mỗi truy vấn $C(n, k)$ chỉ tốn 2 phép nhân, $O(1)$. Em chạy tay với $N$ nhỏ để thấy hai mảng được điền thế nào:
Xem code C++ / Python: tổ hợp C(n, k) mod p với n tới 10^6, nhiều truy vấn (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
const int MAXN = 1000000;
long long fact[MAXN + 1], inv[MAXN + 1]; // inv[i] = (i!)^(-1) mod p
long long power(long long a, long long b){
long long res = 1;
a %= MOD;
while(b > 0){
if(b & 1) res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}
long long C(int n, int k){
if(k < 0 || k > n) return 0;
return fact[n] * inv[k] % MOD * inv[n - k] % MOD;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
fact[0] = 1;
for(int i = 1; i <= MAXN; i++) fact[i] = fact[i - 1] * i % MOD;
inv[MAXN] = power(fact[MAXN], MOD - 2); // một lần lũy thừa nhanh
for(int i = MAXN; i >= 1; i--) inv[i - 1] = inv[i] * i % MOD;
int Q;
cin >> Q;
while(Q--){
int n, k;
cin >> n >> k;
cout << C(n, k) << "\n";
}
return 0;
}import sys
MOD = 10**9 + 7
data = sys.stdin.buffer.read().split()
Q = int(data[0])
qs = [(int(data[1 + 2 * i]), int(data[2 + 2 * i])) for i in range(Q)]
N = max(n for n, k in qs)
fact = [1] * (N + 1)
for i in range(1, N + 1):
fact[i] = fact[i - 1] * i % MOD
inv = [1] * (N + 1)
inv[N] = pow(fact[N], MOD - 2, MOD) # một lần lũy thừa nhanh
for i in range(N, 0, -1):
inv[i - 1] = inv[i] * i % MOD
def C(n, k):
if k < 0 or k > n:
return 0
return fact[n] * inv[k] % MOD * inv[n - k] % MOD
print('\n'.join(str(C(n, k)) for n, k in qs))| Cách | Chuẩn bị | Mỗi truy vấn | Bộ nhớ | Điều kiện modulo |
|---|---|---|---|---|
| Tam giác Pascal | $O(n^2)$ | $O(1)$ | $O(n^2)$ | bất kỳ |
| Giai thừa + nghịch đảo | $O(n + \log p)$ | $O(1)$ | $O(n)$ | $p$ nguyên tố, $p > n$ |
| Tính thẳng bằng số lớn | – | $O(n)$ phép nhân số lớn | – | chỉ khi $n$ rất nhỏ (Python) |
Bảng 5. Chọn cách tính $C(n, k)$: $n \le 5000$ hoặc modulo không nguyên tố thì dùng Pascal; $n$ tới $10^6$, modulo nguyên tố thì dùng giai thừa.
fact[n] = 0 và inv sai hết. Với $p = 10^9 + 7$ và $n \le 10^6$ thì không bao giờ gặp, nhưng nếu đề cho modulo nhỏ như $p = 13$ thì em phải dùng Pascal (khi $n$ nhỏ) hoặc định lý Lucas (nằm ngoài bài học này). Luôn đọc kỹ modulo trong đề!Phần 5Một số bài đếm kinh điển
Có công cụ tính $C(n, k)$ trong tay, rất nhiều bài đếm chỉ còn là việc nhìn ra công thức. Dưới đây là những mô hình gặp nhiều nhất.
1. Đường đi trên lưới. Từ góc trái trên của lưới gồm $m$ hàng ô và $n$ cột ô, đi tới góc phải dưới theo các đường kẻ, mỗi bước sang phải (P) hoặc xuống (X). Mọi đường đi đều gồm đúng $n$ bước P và $m$ bước X, chỉ khác nhau ở vị trí của các bước X trong dãy $m + n$ bước. Vậy số đường đi là
$C(m + n, m) = C(m + n, n)$.
Hình 2. Số ghi ở mỗi điểm là số đường đi từ A tới điểm đó, bằng tổng số ở điểm bên trái và điểm bên trên. Đó chính là tam giác Pascal đặt nghiêng! Lưới 3 hàng × 4 cột có $C(7, 3) = 35$ đường đi.
2. Chia kẹo (bài toán “sao và vạch”). Chia $n$ viên kẹo giống nhau cho $k$ bạn, bạn nào cũng có thể nhận 0 viên. Xếp $n$ viên kẹo (sao ★) thành hàng và chèn $k - 1$ vạch ngăn (|): kẹo trước vạch đầu là của bạn 1, giữa vạch 1 và vạch 2 là của bạn 2, … Ví dụ $n = 5, k = 3$: “★★|★|★★” là chia (2, 1, 2), còn “|★★★★★|” là (0, 5, 0). Mỗi cách chia ứng với đúng một cách chọn vị trí $k - 1$ vạch trong $n + k - 1$ ô, nên số cách là
$C(n + k - 1, k - 1)$.
Nếu mỗi bạn phải nhận ít nhất 1 viên: phát trước cho mỗi bạn 1 viên, còn $n - k$ viên chia tự do: $C(n - 1, k - 1)$. Đây cũng là số nghiệm nguyên không âm của phương trình $x_1 + x_2 + \cdots + x_k = n$.
3. Hoán vị lặp. Có bao nhiêu xâu khác nhau tạo được bằng cách đảo chữ “BANANA”? Nếu 6 chữ cái khác nhau thì có $6!$ cách. Nhưng 3 chữ A đổi chỗ cho nhau không tạo ra xâu mới (bị đếm lặp $3!$ lần), 2 chữ N cũng vậy ($2!$ lần). Vậy có
$\dfrac{6!}{3! \cdot 2! \cdot 1!} = \dfrac{720}{12} = 60$ xâu.
Tổng quát: $\frac{n!}{c_1!\, c_2! \cdots c_t!}$ với $c_i$ là số lần xuất hiện của từng loại. Tính bằng fact và inv như phần 4.
4. Nguyên lý bù trừ. Với hai tập hợp: $|A \cup B| = |A| + |B| - |A \cap B|$ (cộng hai tập thì phần chung bị đếm hai lần, phải trừ đi một lần). Ví dụ đếm số từ 1 tới 100 chia hết cho 2 hoặc 3: $50 + 33 - 16 = 67$ (16 số chia hết cho cả hai, tức là chia hết cho 6). Với nhiều tập thì cộng các giao lẻ tập, trừ các giao chẵn tập.
Bù trừ thường dùng để đếm “phần bù”: khó đếm trực tiếp cách tốt thì đếm tất cả rồi trừ các cách xấu. Ví dụ chia $n$ viên kẹo cho $k$ bạn mà mỗi bạn không quá $u$ viên. Gọi $A_i$ là các cách mà bạn $i$ nhận $\ge u + 1$ viên (cách xấu). Số cách mà một nhóm $j$ bạn cố định đều bị “vượt” tính được dễ dàng: phát trước cho mỗi bạn trong nhóm $u + 1$ viên, phần còn lại chia tự do. Theo bù trừ:
$\displaystyle \text{đáp án} = \sum_{j=0}^{k} (-1)^j \, C(k, j) \, C\big(n - j(u+1) + k - 1,\; k - 1\big)$.
Thử $n = 5, k = 3, u = 2$: $j = 0$ cho $C(7, 2) = 21$; $j = 1$ cho $3 \cdot C(4, 2) = 18$; $j = 2$ cần $5 - 6 < 0$ viên nên bằng 0. Đáp án $21 - 18 = 3$: đó là (2, 2, 1), (2, 1, 2), (1, 2, 2).
Xem code C++ / Python: chia kẹo có giới hạn trên bằng nguyên lý bù trừ (bấm để mở)
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
const int MAXN = 400005;
long long fact[MAXN], inv[MAXN];
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;
}
long long C(long long n, long long k){
if(k < 0 || k > n || n < 0) return 0;
return fact[n] * inv[k] % MOD * inv[n - k] % MOD;
}
int main(){
long long n, k, u; // n kẹo, k bạn, mỗi bạn không quá u viên
cin >> n >> k >> u;
fact[0] = 1;
for(int i = 1; i < MAXN; i++) fact[i] = fact[i - 1] * i % MOD;
inv[MAXN - 1] = power(fact[MAXN - 1], MOD - 2);
for(int i = MAXN - 1; i >= 1; i--) inv[i - 1] = inv[i] * i % MOD;
long long ans = 0;
for(long long j = 0; j <= k && j * (u + 1) <= n; j++){
// j bạn bị "vượt" (nhận ≥ u + 1): chọn j bạn, phát trước mỗi bạn u + 1 viên
long long ways = C(k, j) * C(n - j * (u + 1) + k - 1, k - 1) % MOD;
if(j % 2 == 0) ans = (ans + ways) % MOD;
else ans = (ans - ways + MOD) % MOD;
}
cout << ans;
return 0;
}MOD = 10**9 + 7
n, k, u = map(int, input().split()) # n kẹo, k bạn, mỗi bạn không quá u viên
N = n + k
fact = [1] * (N + 1)
for i in range(1, N + 1):
fact[i] = fact[i - 1] * i % MOD
inv = [1] * (N + 1)
inv[N] = pow(fact[N], MOD - 2, MOD)
for i in range(N, 0, -1):
inv[i - 1] = inv[i] * i % MOD
def C(a, b):
if b < 0 or b > a or a < 0:
return 0
return fact[a] * inv[b] % MOD * inv[a - b] % MOD
ans, j = 0, 0
while j <= k and j * (u + 1) <= n:
ways = C(k, j) * C(n - j * (u + 1) + k - 1, k - 1) % MOD
ans += ways if j % 2 == 0 else -ways
j += 1
print(ans % MOD)| Bài toán | Công thức | Ví dụ |
|---|---|---|
| Đường đi trên lưới $m \times n$ ô (phải / xuống) | $C(m + n, n)$ | $3 \times 4$: $C(7, 4) = 35$ |
| Chia $n$ kẹo cho $k$ bạn, được nhận 0 | $C(n + k - 1, k - 1)$ | $n = 5, k = 3$: $C(7, 2) = 21$ |
| Chia $n$ kẹo cho $k$ bạn, mỗi bạn $\ge 1$ | $C(n - 1, k - 1)$ | $n = 5, k = 3$: $C(4, 2) = 6$ |
| Hoán vị lặp | $\frac{n!}{c_1! \cdots c_t!}$ | BANANA: $60$ |
| Tập con của tập $n$ phần tử | $2^n = \sum_k C(n, k)$ | $n = 4$: $1 + 4 + 6 + 4 + 1 = 16$ |
| Mỗi bạn không quá $u$ viên | bù trừ (ở trên) | $n = 5, k = 3, u = 2$: $3$ |
Bảng 6. Các mô hình đếm hay gặp. Khi gặp bài đếm mới, hãy thử “dịch” nó về một trong các mô hình này.
fact, inv và lấy dư cẩn thận.- Two Sets II (Trung bình)
- Tổng Bình Phương Các Số Con (Trung bình)
- Tích Các Ước (MULDIV) (Khá)
- Tính tổng (OLP2B) (Khá)
- Bộ Vũ Khí Tốt (Codeforces 145C) (Khá)
- Số Cách Điền Lưới (Khó)
- Count Ways to Build Rooms in an Ant Colony (LeetCode 1916) (Khó)
Bài tậpLuyện modulo và tổ hợp
Có $T$ truy vấn ($T \le 10^5$), mỗi truy vấn gồm ba số nguyên $a, b, m$ ($0 \le a, b \le 10^{18}$, $1 \le m \le 10^{18}$). Với mỗi truy vấn, in $a^b \bmod m$ trên một dòng. Quy ước $0^0 = 1$.
3
2 10 1000
3 200 1000000000000000000
5 0 124
182994384699044001
0📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
long long. Trong C++ ép sang __int128 trước khi nhân: (__int128)res * a % m. Trong Python chỉ cần pow(a, b, m). Truy vấn 3: $m = 1$ thì mọi số đều chia hết cho 1, đáp án 0, nên res phải khởi tạo bằng 1 % m.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mulmod(ll a, ll b, ll m){ return (ll)((__int128)a * b % m); }
ll power(ll a, ll b, ll m){
ll res = 1 % m;
a %= m;
while(b > 0){
if(b & 1) res = mulmod(res, a, m);
a = mulmod(a, a, m);
b >>= 1;
}
return res;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int T;
cin >> T;
while(T--){
ll a, b, m;
cin >> a >> b >> m;
cout << power(a, b, m) << "\n";
}
return 0;
}import sys
data = sys.stdin.buffer.read().split()
T = int(data[0])
out = []
for i in range(T):
a, b, m = int(data[1 + 3 * i]), int(data[2 + 3 * i]), int(data[3 + 3 * i])
out.append(pow(a, b, m))
print('\n'.join(map(str, out)))Có $Q$ truy vấn ($Q \le 10^5$), mỗi truy vấn gồm hai số $n, k$ ($0 \le n \le 10^6$, $0 \le k \le 10^6$). In $C(n, k) \bmod (10^9 + 7)$, quy ước $C(n, k) = 0$ khi $k > n$.
4
5 2
10 3
3 5
1000000 210
120
0
999496507📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
fact và inv một lần cho tới $10^6$, mỗi truy vấn chỉ 2 phép nhân. Nếu với mỗi truy vấn lại gọi lũy thừa nhanh hay vòng lặp tính giai thừa, $10^5$ truy vấn sẽ chậm. $C(10^6, 2) = \frac{10^6 \cdot 999\,999}{2} = 499\,999\,500\,000$, lấy dư $10^9 + 7$ được $999\,496\,507$.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
const int MAXN = 1000000;
long long fact[MAXN + 1], inv[MAXN + 1];
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(){
ios::sync_with_stdio(false); cin.tie(nullptr);
fact[0] = 1;
for(int i = 1; i <= MAXN; i++) fact[i] = fact[i - 1] * i % MOD;
inv[MAXN] = power(fact[MAXN], MOD - 2);
for(int i = MAXN; i >= 1; i--) inv[i - 1] = inv[i] * i % MOD;
int Q;
cin >> Q;
while(Q--){
int n, k;
cin >> n >> k;
if(k > n) cout << 0 << "\n";
else cout << fact[n] * inv[k] % MOD * inv[n - k] % MOD << "\n";
}
return 0;
}import sys
MOD = 10**9 + 7
data = sys.stdin.buffer.read().split()
Q = int(data[0])
qs = [(int(data[1 + 2 * i]), int(data[2 + 2 * i])) for i in range(Q)]
N = max(n for n, k in qs)
fact = [1] * (N + 1)
for i in range(1, N + 1):
fact[i] = fact[i - 1] * i % MOD
inv = [1] * (N + 1)
inv[N] = pow(fact[N], MOD - 2, MOD)
for i in range(N, 0, -1):
inv[i - 1] = inv[i] * i % MOD
out = []
for n, k in qs:
out.append(0 if k > n else fact[n] * inv[k] % MOD * inv[n - k] % MOD)
print('\n'.join(map(str, out)))Một robot ở ô $(1, 1)$ của bảng $m$ hàng, $n$ cột ($2 \le m, n \le 10^6$), cần tới ô $(m, n)$. Mỗi bước robot sang phải một ô hoặc xuống một ô. Ô $(u, v)$ bị hỏng, robot không được đi qua (ô hỏng khác ô xuất phát và ô đích). Đếm số đường đi, in theo modulo $10^9 + 7$.
3 3
2 22📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
MOD.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
const int MAXN = 2000005;
long long fact[MAXN], inv[MAXN];
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;
}
long long C(int n, int k){
if(k < 0 || k > n) return 0;
return fact[n] * inv[k] % MOD * inv[n - k] % MOD;
}
int main(){
int m, n, u, v;
cin >> m >> n >> u >> v;
int N = m + n;
fact[0] = 1;
for(int i = 1; i <= N; i++) fact[i] = fact[i - 1] * i % MOD;
inv[N] = power(fact[N], MOD - 2);
for(int i = N; i >= 1; i--) inv[i - 1] = inv[i] * i % MOD;
long long all = C(m + n - 2, m - 1);
long long bad = C(u + v - 2, u - 1) * C(m - u + n - v, m - u) % MOD;
cout << (all - bad + MOD) % MOD;
return 0;
}MOD = 10**9 + 7
m, n = map(int, input().split())
u, v = map(int, input().split())
N = m + n
fact = [1] * (N + 1)
for i in range(1, N + 1):
fact[i] = fact[i - 1] * i % MOD
inv = [1] * (N + 1)
inv[N] = pow(fact[N], MOD - 2, MOD)
for i in range(N, 0, -1):
inv[i - 1] = inv[i] * i % MOD
def C(a, b):
if b < 0 or b > a:
return 0
return fact[a] * inv[b] % MOD * inv[a - b] % MOD
total = C(m + n - 2, m - 1)
bad = C(u + v - 2, u - 1) * C(m - u + n - v, m - u) % MOD
print((total - bad) % MOD)Cô giáo có $n$ viên kẹo giống nhau, chia hết cho $k$ bạn học sinh sao cho mỗi bạn nhận ít nhất $L$ viên ($1 \le n, k \le 10^6$, $0 \le L \le 10^6$). Hai cách chia khác nhau nếu có một bạn nhận số kẹo khác nhau. Đếm số cách chia, in theo modulo $10^9 + 7$.
7 3 115📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
long long). Còn lại $r = n - kL$ viên chia tự do (được nhận 0) cho $k$ bạn: mô hình sao và vạch, $C(r + k - 1, k - 1)$. Ví dụ: $r = 7 - 3 = 4$, đáp án $C(6, 2) = 15$.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
const int MAXN = 2000005;
long long fact[MAXN], inv[MAXN];
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(){
long long n, k, L;
cin >> n >> k >> L;
if(n < k * L){ cout << 0; return 0; }
long long r = n - k * L; // số kẹo còn lại, chia tự do
int N = r + k - 1;
fact[0] = 1;
for(int i = 1; i <= N; i++) fact[i] = fact[i - 1] * i % MOD;
inv[N] = power(fact[N], MOD - 2);
for(int i = N; i >= 1; i--) inv[i - 1] = inv[i] * i % MOD;
cout << fact[N] * inv[k - 1] % MOD * inv[N - (k - 1)] % MOD; // C(r + k - 1, k - 1)
return 0;
}MOD = 10**9 + 7
n, k, L = map(int, input().split())
if n < k * L:
print(0)
else:
r = n - k * L # số kẹo còn lại, chia tự do
N = r + k - 1
fact = [1] * (N + 1)
for i in range(1, N + 1):
fact[i] = fact[i - 1] * i % MOD
# C(N, k - 1) = N! / ((k - 1)! * r!)
den = fact[k - 1] * fact[r] % MOD
print(fact[N] * pow(den, MOD - 2, MOD) % MOD)Đếm số xâu nhị phân độ dài $n$ có đúng $k$ chữ số 1 và không có hai chữ số 1 nào đứng cạnh nhau ($1 \le n \le 10^6$, $0 \le k \le 10^6$). In theo modulo $10^9 + 7$.
5 26📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
long long fact[1000005];
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(){
long long n, k;
cin >> n >> k;
long long slots = n - k + 1; // số khe giữa các chữ số 0
if(k > n || k > slots){ cout << 0; return 0; }
fact[0] = 1;
for(int i = 1; i <= slots; i++) fact[i] = fact[i - 1] * i % MOD;
long long den = fact[k] * fact[slots - k] % MOD;
cout << fact[slots] * power(den, MOD - 2) % MOD; // C(slots, k)
return 0;
}MOD = 10**9 + 7
n, k = map(int, input().split())
slots = n - k + 1 # số khe giữa các chữ số 0
if k > n or k > slots:
print(0)
else:
fact = [1] * (slots + 1)
for i in range(1, slots + 1):
fact[i] = fact[i - 1] * i % MOD
den = fact[k] * fact[slots - k] % MOD
print(fact[slots] * pow(den, MOD - 2, MOD) % MOD) # C(slots, k)Cho xâu $s$ gồm chữ cái thường, độ dài không quá $10^6$. Đếm số xâu khác nhau thu được khi hoán đổi vị trí các chữ cái của $s$ (tính cả chính $s$). In theo modulo $10^9 + 7$.
banana60📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
fact tới $n$, nhân tất cả $c_x!$ ở mẫu lại rồi nhân với nghịch đảo của mẫu (một lần lũy thừa nhanh). “banana” có $n = 6$, ba chữ a, hai chữ n, một chữ b: $\frac{720}{6 \cdot 2 \cdot 1} = 60$.Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
long long fact[1000005];
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(){
string s;
cin >> s;
int n = s.size();
fact[0] = 1;
for(int i = 1; i <= n; i++) fact[i] = fact[i - 1] * i % MOD;
int cnt[26] = {0};
for(char c : s) cnt[c - 'a']++;
long long den = 1;
for(int c = 0; c < 26; c++) den = den * fact[cnt[c]] % MOD;
cout << fact[n] * power(den, MOD - 2) % MOD;
return 0;
}import sys
from collections import Counter
MOD = 10**9 + 7
s = sys.stdin.readline().strip()
n = len(s)
fact = [1] * (n + 1)
for i in range(1, n + 1):
fact[i] = fact[i - 1] * i % MOD
den = 1
for c in Counter(s).values():
den = den * fact[c] % MOD
print(fact[n] * pow(den, MOD - 2, MOD) % MOD)Có $T$ truy vấn ($T \le 10^5$). Mỗi truy vấn cho ba số $a, b, m$ ($1 \le a \le 10^9$, $1 \le m \le 10^9$, $0 \le b < m$, $m$ không nhất thiết nguyên tố). Tìm số nguyên $x$ nhỏ nhất trong $[0, m)$ sao cho $a \cdot x \equiv b \pmod m$, hoặc in $-1$ nếu không có.
3
4 6 10
3 5 7
6 4 94
4
-1📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll extgcd(ll a, ll b, ll &x, ll &y){
if(b == 0){ x = 1; y = 0; return a; }
ll x1, y1;
ll g = extgcd(b, a % b, x1, y1);
x = y1;
y = x1 - (a / b) * y1;
return g;
}
int main(){
ios::sync_with_stdio(false); cin.tie(nullptr);
int T;
cin >> T;
while(T--){
ll a, b, m;
cin >> a >> b >> m;
ll x, y;
ll g = extgcd(a, m, x, y); // a*x + m*y = g
if(b % g != 0){ cout << -1 << "\n"; continue; }
ll m2 = m / g;
ll inv = (x % m2 + m2) % m2; // nghịch đảo của a/g theo modulo m/g
cout << (b / g) % m2 * inv % m2 << "\n";
}
return 0;
}import sys
def extgcd(a, b):
if b == 0:
return a, 1, 0
g, x1, y1 = extgcd(b, a % b)
return g, y1, x1 - (a // b) * y1
data = sys.stdin.buffer.read().split()
T = int(data[0])
out = []
for i in range(T):
a, b, m = int(data[1 + 3 * i]), int(data[2 + 3 * i]), int(data[3 + 3 * i])
g, x, y = extgcd(a, m) # a*x + m*y = g
if b % g:
out.append(-1)
else:
m2 = m // g
out.append((b // g) * x % m2) # x là nghịch đảo của a/g theo modulo m/g
print('\n'.join(map(str, out)))Dãy ngoặc đúng là dãy gồm các ký tự ( và ) mà mỗi ngoặc mở đều có một ngoặc đóng tương ứng phía sau, ví dụ (())(). Đếm số dãy ngoặc đúng gồm $n$ cặp ngoặc ($1 \le n \le 10^6$), in theo modulo $10^9 + 7$.
35📝 Nộp bài, chấm tự động trên ClueOJ ↗
💡 Gợi ý
Xem code tham khảo (C++ / Python)
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
long long fact[2000005];
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 n;
cin >> n;
fact[0] = 1;
for(int i = 1; i <= 2 * n; i++) fact[i] = fact[i - 1] * i % MOD;
// Catalan(n) = (2n)! / (n! * (n + 1)!)
long long den = fact[n] * fact[n + 1] % MOD;
cout << fact[2 * n] * power(den, MOD - 2) % MOD;
return 0;
}MOD = 10**9 + 7
n = int(input())
fact = [1] * (2 * n + 1)
for i in range(1, 2 * n + 1):
fact[i] = fact[i - 1] * i % MOD
# Catalan(n) = (2n)! / (n! * (n + 1)!)
den = fact[n] * fact[n + 1] % MOD
print(fact[2 * n] * pow(den, MOD - 2, MOD) % MOD)
- Không biết học gì trước, học gì sau, học lan man nên kiến thức bị hổng.
- Bí bài không ai gỡ, ngồi cả buổi vẫn không ra rồi bỏ cuộc.
- Code chạy được nhưng không đủ điểm, không biết sai ở đâu, chậm ở đâu.
- Không có đề thi thử và người chấm, nên không biết mình đang ở mức nào.
- Dễ nản giữa chừng khi không có ai theo sát.
- Lộ trình 111 buổi video sắp sẵn từ dòng code đầu tiên đến đề HSG thật của các tỉnh.
- Thầy trực tiếp gỡ bí, chữa bài cho từng em qua nhóm Zalo riêng.
- Hệ thống chấm bài tự động 24/7 và thi thử HSG hằng tuần để biết chính xác mình đang ở đâu.
- Đóng học phí một lần, thầy kèm lâu dài: từ thi chuyên Tin đến HSG quốc gia và cả khi lên đại học.
Nhận xét
Đăng nhận xét