Tất tần tật về cách tìm $C^k_n$
Định nghĩa
$C^k_n$ là số cách chọn $k$ phần tử phân biệt từ tập hợp $n$ phần tử phân biệt cho trước mà không phân biệt thứ tự. Ví dụ cho tập hợp $S = (1, 2, 3, 4)$ gồm $4$ phần tử, các cách chọn ra tập hợp con gồm 3 phần tử là $(1,, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)$, tương đương với $C^3_4 = 3$
Công thức được định nghĩa như sau:
\[C^k_n = \frac{n!}{k!(n - k)!}(1)\]Cách tìm $C^k_n$
Cách 1. Tính trực tiếp
Sử dụng trực tiếp công thức $(1)$
1
2
3
4
5
6
7
8
9
10
11
12
13
int ans = 1;
for (int i = 1; i <= n; i++){
ans = ans * i;
}
for (int i = 1; i <= k; i++){
ans = ans / i;
}
for (int i = 1; i <= n - k; i++){
ans = ans / i;
}
cout << ans << endl;
Ưu điểm
- Trực diện, dễ code
Nhược điểm
- Trực diện (yes).
- Hầu như không thể áp dụng với các bài tập vì quá đơn giản.
Từ cách 2 trở đi, mình sẽ tính các giá trị $C^k_n \; mod \; M$ vì các giá trị $C_n^k$ với $n, k$ lớn sẽ vượt qua giới hạn của $long \; long$.
Cách 2. Sử dụng công thức truy hồi (Pascal Triangle)
\[C^k_n=C^k_{n-1} + C^{k-1}_{n-1}\]Giải thích:
- Ta sẽ dùng định nghĩa của $C^k_n$ để giải thích công thức trên.
- Theo định nghĩa, $C^k_n$ là số cách chọn $k$ phần tử từ $n$ phần tử. Giả sử ta đã xét chọn $n-1$ phần tử đầu tiên, và ta sẽ xét phần tử thứ $n$, có hai trường hợp xảy ra:
- Chọn phần tử thứ $n$: vậy trước đó ta sẽ phải chọn $k-1$ phần tử từ tập $n-1$ phần tử đầu tiên.
- Không chọn phần tử $n$: trước đó ta đã phải chọn đủ $k$ phần tử từ $n-1$ phần tử đầu tiên.
Code
1
2
3
4
5
6
7
8
9
10
11
12
int c[][];
int MOD;
for (int i = 0; i <= n; i++){
for (int j = 0; j <= i; j++){
if (j == 0 || j == i) c[i][j] = 1;
else{
c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
c[i][j] %= MOD;
}
}
cout << c[n][k] << endl;
}
Độ phức tạp
- Tiền xử lí: $O(n^2)$.
- Truy vấn: $O(1)$.
Ưu điểm
- Có thể thực hiện với $n \le 5000$.
- Lưu được nhiều giá trị $C^k_n$ vào bộ nhớ, tìm được giá trị $C^k_n$ nhiều lần với độ phức tạp $O(1)$ mỗi lần truy cập.
- Có thể sử dụng với $MOD$ không nguyên tố.
Nhược điểm
- Với những bài tập có $n$ tương đối lớn $(n \le 10^7)$ sẽ không thể sử dụng.
Cách 3. Sử dụng sàng nguyên tố
Xét công thức $(1)$:
\[C^k_n = \frac{n!}{k!(n-k)!}\]Ta sẽ phân tích $C^k_n = p_1^{a_1} \times p_2^{a_2} \times … \times p_x^{a_x}$
Trước tiên ta sẽ sàng nguyên tố và sử dụng mảng $cnt[i]$ là giá trị mũ của số nguyên tố $i$ trong cách phân tích trên. Lần lượt phân tích $n!, k!$ và $(n-k)!$ trong $O(nlog(n))$. Với mỗi thừa số $i$ nguyên tố của $n!$, ta tăng giá trị của $cnt[i]$ lên $1$. Với mỗi thừa số $i$ nguyên tố của $k!$ hoặc $(n-k)!$, ta giảm giá trị của $cnt[i]$ đi $1$.
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
int sieve[]; // mảng sàng nguyên tố
int cnt[];
int MOD;
void factorize(int x, int coef){
while (x > 1){
cnt[sieve[x]] += coef;
x = sieve[x];
}
};
int binpow(int x, int y){
if (y == 0) return 1;
int t = binpow(x, y / 2);
t = (t * t) % MOD;
if (t % 2 == 1) t = (t * x) % MOD;
return t;
}
for (int i = 1; i <= n; i++){
factorize(i, 1);
}
for (int i = 1; i <= k; i++){
factorize(i, -1);
}
for (int i = 1; i <= n - k; i++){
factorize(i, -1);
}
for (int i = 1; i <= n; i++){
res = res * binpow(i, cnt[i]);
res %= MOD;
}
cout << res << endl;
Độ phức tạp
- Tiền xử lí: $O(1)$.
- Truy vấn: $O(nlog(n))$.
Ưu điểm
- Có thể sử dụng với $n, k$ lớn $(1 \le k \le n \le 10^7)$.
- Có thể sử dụng được với $MOD$ không nguyên tố.
Nhược điểm
- Không sử dụng được trong những bài tập có nhiều truy vấn.
Cách 4. Sử dụng tính chất thừa số chung ở tử số và mẫu số
Ta sẽ phân tích công thức $(1)$:
\[C^k_n=\frac{n!}{k!(n-k)!}=\frac{(n-k+1)(n-k+2)...n}{k!}\]Xét với $mod \; M$ nguyên tố, ta có thể dễ dàng tìm được giá trị của tử số và mẫu số trong $O(k)$, gọi là $a$ và $b$. Đáp án sẽ là $a$ $\times$ $b^{-1} \; \% \; MOD$ hay $a$ $\times$ $b^{MOD-2} \; \% \; MOD$.
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int num = 1, den = 1;
int MOD;
int binpow(int x, int y){
if (y == 0) return 1;
int t = binpow(x, y / 2);
t = (t * t) % MOD;
if (t % 2 == 1) t = (t * x) % MOD;
return t;
}
for (int i = n - k + 1; i <= n; i++){
num = (num * i) % MOD;
}
for (int i = 1; i <= k; i++){
den = (den * i) % MOD;
}
den = binpow(den, MOD - 2);
cout << (num * den) % MOD << endl;
Độ phức tạp
- Tiền xử lí: $O(1)$.
- Truy vấn: $O(k)$.
Ưu điểm
- Sử dụng được với $n$ rất lớn, $k$ lớn ($n \le 10^{18}, k \le 10^7$).
- Cài đặt tương đối dễ.
Nhược điểm
- Chỉ sử dụng được với $MOD$ nguyên tố.
- Không sử dụng được trong những bài tập có nhiều truy vấn.
Cách 5. Tính trước giá trị của giai thừa
Ta có:
\[C^k_n = \frac{n!}{k!(n-k)!} \equiv n! \times k!^{-1} \times (n-k)!^{-1} \equiv n! \times k!^{MOD-2} \times (n-k)!^{MOD - 2} \; mod \; M\]với $M$ nguyên tố và $M > max(k, n - k)$.
Chuẩn bị mảng $fac[i]$ là giá trị của $i!$, $rfac[i]$ là giá trị của $i!^{-1}$ trong $O(nlog(n))$. Từ đó $C^k_n=fac[n] \times ifac[k] \times ifac[n-k] \; mod \; M$.
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int fac[], rfac[];
int MOD;
fac[0] = 1;
auto binpow = [&] (int x, int y){
if (y == 0) return 1;
int t = binpow(x, y / 2);
t = t * t;
if (t % 2 == 1) t = t * x;
return t;
}
for (int i = 1; i <= n; i++) fac[i] = (fac[i - 1] * i) % MOD;
rfac[n] = binpow(fac[n], MOD - 2); // (n!)^(-1) = (n!)^(MOD - 2)
for (int i = n; i >= 1; i--){
rfac[i - 1] = (rfac[i] * i) % MOD;
// ((n-1)!)^(-1) = (n!)^(-1) * n
}
cout << (fac[n] * ifac[k]) % MOD * ifac[n - k] % MOD << endl;
Độ phức tạp:
- Tiền xử lí: $O(n)$
- Truy vấn: $O(1)$
Ưu điểm
- Dễ code, có thể sử dụng trong các bài tập nhiều truy vấn, với mỗi lần tìm $C^k_n$ trong $O(1)$.
- Là cách sử dụng khá phổ biển.
Nhược điểm
- Không sử dụng được với $MOD$ nguyên tố.
Cách 6. Sử dụng định lí Lucas
Xét $M$ là số nguyên tố, ta có:
\[C^k_n \equiv \prod_{i=0}^{p}C^{k_i}_{n_i} \; mod \; M\]với $n = n_pM^p + n_{p-1}M^{p-1} + … + n_1M + n_0$, $k=k_pM^p + k_{p-1}M^{p-1}+…+k_1M + k_0$.
Ta đã chia nhỏ bài toán $C^k_n$ thành tối đa $\log_{M}{n}$ bài toán con, với $k_i, n_i < M \;$ $\forall 1 \le i \le p$. Với $M$ đủ nhỏ (lí tưởng là $M \le 10^6$), ta có thể tính $C^{k_i}_{n_i}$ sử dụng cách 5.
Chứng minh (Nguồn: Wikipedia)
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int fac[], rfac[]; // cài đặt và sử dụng như cách 5
int MOD;
fac[0] = 1;
auto C = [&](int n, int k){
return fac[n] * ifac[k] % MOD * ifac[n - k] % MOD;
}
auto convertToBaseM = [&](int val){
vector<int> res;
while (val){
res.push_back(val % MOD);
val /= MOD;
}
return res;
}
vector<int> N = convertToBaseM(n);
vector<int> K = convertToBaseM(k);
int res = 1;
for (int i = 0; i < K.size(); i++){
res = (res * C(N[i], K[i])) % MOD;
}
cout << res << endl;
Độ phức tạp
Với những bài các truy vấn có cùng $mod \; M$
- Tiền xử lí: $O(M)$.
- Truy vấn: $O(log_Mn)$.
Với những bài các truy vấn không có cùng $mod \; M$
- Tiền xử lí: $O(1)$.
- Truy vấn: $O(M)$.
Ưu điểm
- Có thể làm được với $n, k$ rất lớn $(1 \le k \le n \le 10^{18})$.
- Có thể sử dụng với những bài có nhiều truy vấn $(n, k)$ và $M$ cố định với mỗi lần tìm $C_n^k$ trong $O(log_Mn)$.
- Cài đặt tương đối gọn và đơn giản.
Nhược điểm
- Chỉ sử dụng được với $MOD$ nguyên tố và không được quá lớn. Lí tưởng là $MOD \le 10^6$.
Cách 7. Sử dụng định lí Lucas và định lí Thặng dư Trung Hoa
Xét $M$ là số nguyên tố cố dạng:
\[M=p_1p_2...p_m\]Đây chính là số square-free
Ta sẽ tìm $C^k_n \; mod \; p_1$, $C^k_n \; mod \; p_2$, …, $C^k_n \; mod \; p_m$ sử dụng Định lí Lucas như cách 6 kết hợp với Định lí Thặng dư Trung Hoa để tìm được $C^k_n \; mod \; M$.
Đối với $M$ bất kì, tức $M$ có dạng:
\[M=p_1^{q_1}p_2^{q_2}...p_m^{q_m}\]Tương đương như trên, ta sẽ tìm $C^k_n \; mod \; p_1^{q_1}$, $C^k_n \; mod \; p_2^{q_2}$, …, $C^k_n \; mod \; p_m^{q_m}$. Để tìm được, bạn đọc có thể tự tìm hiểu ở đây, là một dạng tổng quát của định lí Lucas, tương đối phức tạp nên mình sẽ không nói trong bài viết này. Sau khi tìm được, ta cũng sử dụng Định lí Thặng dư Trung Hoa để tìm được $C^k_n \; mod \; M$
Ưu điểm
- Tìm được $C^k_n$ với $n, k$ lớn $(1 \le k \le n \le 10^{18})$ với $MOD$ không cần nguyên tố.
Nhược điểm
- Cài đặt tương đối khó và dài.
Cách 8. Sử dụng cách phân tích $n! = a \times p^b$
Ta tiếp tục xét bài toán với $mod \; M$ bất kì, $M$ có dạng:
\[M=p_1^{q_1}p_2^{q_2}...p_m^{q_m}\]Ta sẽ tìm $C^k_n \; mod \; p_1^{q_1}$, $C^k_n \; mod \; p_2^{q_2}$, …, $C^k_n \; mod \; p_m^{q_m}$. Thay vì sử dụng dạng tổng quát của định lí Lucas để tìm $C_n^k \; mod \; p_x^{q_x}$, ta sẽ biến đổi $C_n^k$ như sau:
\[C^k_n=\frac{n!}{k!(n-k)!}=\frac{f(n)p^{c(n)}}{f(k)p^{c(k)}f(n-k)p^{c(n-k)}}=\frac{f(n)}{f(k)f(n-k)}p^{c(n) - c(k) - c(n - k)}\]với $f(n)p^{c(n)}=n!$ và $gcd(f(n), p)=1$.
Ta có hai bài toán cần giải quyết: tìm $f(n)$ và $c(n)$.
Tìm $c(n)$
- Với $n!$, sẽ có $\lfloor n/p \rfloor$ số chia hết cho $p$. Đó là các dãy các số gồm $p, 2p, 3p, …, \lfloor n/p \rfloor p$ $(*)$.
- Tách $p$ ra khỏi dãy trên ta sẽ có dãy mới gồm $1, 2, 3, …, \lfloor n/p \rfloor$ hay chính là $\lfloor n/p \rfloor !$. Vậy ta sẽ gọi đệ quy xuống $\lfloor n/p \rfloor !$ và lặp lại bước $(*)$. Lưu ý, số lần tối đa ta gọi đệ quy sẽ là $log_pn$.
- Vậy công thức tổng quát của $c(n)$ sẽ là: \(c(n)=\lfloor n/p \rfloor + \lfloor n/p^2 \rfloor + \lfloor n/p^3 \rfloor + \; ... + \lfloor n/p^{\lfloor log_pn \rfloor} \rfloor\)
Đây chính là Legendre’s formula.
Tìm $f(n)$
Ta có $f(n)=\frac{n!}{p^{c(n)}}$. Từ đây, ta sẽ coi như bài toán trở thành tìm giá trị của $n!$ khi loại bỏ hết các thừa số $p$. Xét $A = n!$
\[\displaylines{A=1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-1) \cdot p \cdot (p+1) \cdot \ldots \cdot (2p-1) \cdot 2p \cdot (2p+1)\\\cdot \ldots \cdot (p^2-1) \cdot p^2 \cdot (p^2+1) \cdot \ldots \cdot (n-1) \cdot n}\] \[\displaylines{=1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-1) \cdot (p+1) \cdot \ldots \cdot (2p-1) \cdot (2p+1) \cdot \ldots\\\cdot (p^2-1) \cdot (p^2+1) \cdot \ldots \cdot (n-1) \cdot n \cdot(p \cdot 2p \cdot \ldots \cdot \lfloor n/p \rfloor p)}\] \[\displaylines{=1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-1) \cdot (p+1) \cdot \ldots \cdot (2p-1) \cdot (2p+1) \cdot \ldots\\\cdot (p^2-1) \cdot (p^2+1) \cdot \ldots \cdot (n-1) \cdot n \cdot(1 \cdot 2 \cdot \ldots \cdot \lfloor n/p \rfloor ) \cdot p^{\lfloor n/p \rfloor}}\] \[\displaylines{=1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-1) \cdot (p+1) \cdot \ldots \cdot (2p-1) \cdot (2p+1) \cdot \ldots\\\cdot (p^2-1) \cdot (p^2+1) \cdot \ldots \cdot (n-1) \cdot n \cdot \lfloor n/p \rfloor! \cdot p^{\lfloor n/p \rfloor}}\]Sau khi loại $p^{\lfloor n/p \rfloor}$ ra khỏi $A$, ta cần tìm giá trị của
\[B=1 \cdot 2 \cdot 3 \cdot \ldots \cdot (p-1) \cdot (p+1) \cdot \ldots \cdot (2p-1) \cdot (2p+1) \cdot \ldots \\ \cdot (p^2-1) \cdot (p^2+1) \cdot \ldots \cdot (n-1) \cdot n\] \[C=\lfloor n/p \rfloor!\]- Với $B$, ta lưu $pre[i]$ là tích của $i$ số nguyên dương đầu tiên $mod \; p^q$ ngoại trừ các số chia hết cho $p$. Từ đó $B \equiv pre[p^q-1]^{n / p^q} \times pre[n \; mod \; p^q] \; mod \; p^q$ (Tưởng tượng với $n$ số, ta chia được thành $n/p^q$ phần có tích đồng dư giống nhau và dư ra một đoạn có độ dài $n \; mod \; p^q$) $(**)$.
- Với $C$, tương tự như cách tìm $c(n)$, ta gọi đệ quy để phân tích tiếp $\lfloor n/p \rfloor!$ rồi lặp lại bước $(**)$, và chứng minh được số lần gọi đệ quy là $\lceil log_pn \rceil$.
Sau khi tìm được $f(n)$ và $c(n)$
Ta sẽ tương tư tìm $f(k)$ và $f(n-k)$. Tuy nhiên ta cần tìm $\frac{f(n)}{f(k)f(n-k)}$. Nhận thấy $gcd(f(k), p^q) = 1$ và $gcd(f(n-k), p^q)=1$, sử dụng phi hàm Euler, ta có được công thức sau:
\[\frac{f(n)}{f(k)f(n-k)} \equiv f(n) \times f(k)^{\phi(p^q)-1} \times f(n-k)^{\phi(p^q)-1} \; mod \; p^q\]Vậy bài toán tìm $C^k_n \; mod \; p^q$ đến đây đã được giải quyết. Lưu ý nếu $c(n)-c(k)-c(n-k) \geq q$ thì giá trị tổ hợp sẽ là 0.
Sau khi tìm được tất cả $C^k_n \; mod \; p_x^{q_x}$, ta sẽ sử dụng định lí Thặng dư Trung Hoa để tìm $C^k_n \; mod \; M$
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <bits/stdc++.h>
#define int long long
#define ii pair<int, int>
#define st first
#define nd second
#define endl "\n"
#define all(v) v.begin(), v.end()
#define Unique(v) v.erase(unique(all(v)), v.end())
using namespace std;
const int MAXN = 1e6 + 5;
int prime[MAXN], fac[MAXN], phi[MAXN];
int n, k, MOD;
void sieve(){
for (int i = 2; i * i < MAXN; i++){
if (prime[i]) continue;
for (int j = i * i; j < MAXN; j += i){
if (!prime[j]) prime[j] = i;
}
}
for (int i = 2; i < MAXN; i++) if (!prime[i]) prime[i] = i;
for (int i = 0; i < MAXN; i++) phi[i] = i;
for (int i = 2; i < MAXN; i++){
if (phi[i] == i){
for (int j = i; j < MAXN; j += i) phi[j] -= phi[j] / i;
}
}
}
int binpow (int x, int y, int MOD = 1e9 + 7){
if (y == 0) return 1;
int t = binpow(x, y / 2, MOD);
t = (t * t) % MOD;
if (y & 1) t = (x * t) % MOD;
return t;
}
vector<ii> p;
vector<int> res;
void PROGRAM(int _){
cin >> n >> k >> MOD;
auto factorize = [&] (int val){
while (val > 1){
int t = prime[val], cnt = 0;
while (val % t == 0) val /= t, ++cnt;
p.push_back({t, cnt});
}
};
factorize(MOD);
auto factorize_mod = [&] (int val, int p, int q){
int x = 1, y = 0;
int v = binpow(p, q);
fac[0] = 1;
for (int i = 1; i < v; i++){
fac[i] = fac[i - 1];
if (i % p == 0) continue;
fac[i] = (fac[i - 1] * i) % v;
}
while (val > 1){
y += (val / p); // tìm c(n)
int c = val / v;
c = binpow(fac[v - 1], c, v); // gồm c phần fac[v - 1]
x = (x * c) % v;
x = (x * fac[val % v]) % v; // phần dư ra
val /= p;
}
return (ii){x, y};
};
for (auto [a, q] : p){
int y = 0, val = 1, v = binpow(a, q);
ii k = factorize_mod(n, a, q);
val = (val * k.st) % v; // f(n)
y += k.nd; // c(n)
k = factorize_mod(::k, a, q);
val = (val * binpow(k.st, phi[v] - 1, v)) % v; // f(k)
y -= k.nd; // c(k)
k = factorize_mod(n - ::k, a, q);
val = (val * binpow(k.st, phi[v] - 1, v)) % v; // f(n - k)
y -= k.nd; // c(n - k)
if (y >= q){
res.push_back(0);
continue;
}
res.push_back(val * binpow(a, y, v) % v);
}
int ans = 0;
// Khôi phục nCk sử dụng định lí thặng dư Trung Hoa
for (int i = 0; i < p.size(); i++){
auto [a, q] = p[i];
int v = binpow(a, q);
int val = res[i];
int y = MOD / v;
int z = binpow(y, phi[v] - 1, v);
val = (val * y) % MOD * z % MOD;
ans = (ans + val) % MOD;
}
cout << ans << endl;
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
sieve();
int test = 1;
for (int _ = 1; _ <= test; _++){
PROGRAM(_);
}
return 0;
}
Độ phức tạp
Với những bài các truy vấn có cùng $mod \; M$
- Tiền xử lí: $O(M)$.
- Truy vấn: $O((logM)^2)$.
Với những bài các truy vấn không có cùng $mod \; M$
- Tiền xử lí: $O(1)$.
- Truy vấn: $O(M)$.
Ưu điểm
- Tìm được $C^k_n$ với $n, k$ lớn $(1 \le k \le n \le 10^{18})$ với $MOD$ không cần nguyên tố.
- Dễ hiểu hơn so với cách 7.