Nếu M là số nguyên tố thì CNK≡Cn0k0.Cn1k1...Cnpkp (mod M)
Trong đó:
npnp−1...n0 là dạng biểu diễn của N trên hệ cơ số M
kpkp−1...k0 là dạng biểu diễn của K trên hệ cơ số M
Nói cách khác:
N=n0.M0+n1.M1+...+np.Mp
K=k0.M0+k1.M1+...+kp.Mp
Với M là số nguyên tố và i là số nguyên với 1≤i<M
⇒CMi=i.(i−1)...1M.(M−1)...(M−i+1)≡0 (mod M) do gcd(M,i!)=1
⇒(1+X)M=∑i=0MCMi.Xi≡1+XM (mod M) với mọi X∈Z
Lại có:
(1+XM)M≡((1+X)M)M≡(1+X)M2 (mod M)
và
(1+XM)M≡1+(XM)M≡1+XM2 (mod M)
⇒(1+X)M2≡1+XM2 (mod M)
Cứ tiếp tục như vậy, với mọi i∈N ta được:
(1+X)Mi≡1+XMi (mod M)
Ta có:
∑K=0NCNK.XK
=(1+X)N (nhị thức Newton) (1)
Tách N về dạng cơ số M ta được:
(1)=(1+X)n0.M0+n1.M1+...+np.Mp
=∏i=0p((1+X)Mi)ni
≡∏i=0p(1+XMi)ni (mod M)
=∏i=0p∑ki=0niCnikiXki.Mi (nhị thức Newton)
=∏i=0p∑ki=0M−1CnikiXki.Mi (ni≤M−1 với mọi i và Cji=0 với i>j) (2)
Nhóm các CnikiXki.Mi lại ta có
Cn0k0.Cn1k1...Cnpkp.Xk0.M0+k1.M1+...kp.Mp
Do đó với một bộ (k0,k1,...kp) bất kì ta được một hạng tử
Cn0k0.Cn1k1...Cnpkp.XK
(Cn0k0.Cn1k1...Cnpkp là hệ số của XK)
Vậy (2)=∑K=0N∏i=0pCnikiXK
Từ đó suy ra: ∑K=0NCNK.XK≡∑K=0N∏i=0pCnikiXK (mod M) với mọi X∈Z
⇔CNK≡∏i=0pCniki (mod M)
vector<int> getRepresentation(int N) {
vector<int> res;
while (N > 0) {
res.push_back(N % M);
N /= M;
}
return res;
}
Đoạn code trên chạy trong thời gian O(logMN)
Với N nhỏ ta có thể sử dụng công thức tam giác Pascal để tính trước trong O(n2) và truy vấn trong O(1):
int C[M][M];
for (int i = 0; i < M; ++i) {
for (int j = 0; j <= i; ++j) {
if (i == 0 || j == 0) {
C[i][j] = 1;
} else {
C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % M;
}
}
}
Với M nhỏ các bạn có thể tiền xử lý trong O(M) và truy vấn trong O(logM) bằng trick #3 ở đây.
long long fact[M];
fact[0] = 1;
for (int i = 1; i < M; ++i) {
fact[i] = (fact[i - 1] * i) % M;
}
int C(int N, int K) {
if (K > N) {
return 0;
}
return (((fact[N] * binpow(fact[N - K], M - 2)) % M) * binpow(fact[K], M - 2)) % M;
}
Trong đó hàm binpow(a,n) dùng để tính nhanh an trong O(logn) bằng chia để trị:
an=(an/2)2 nếu n chẵn
an=(an/2)2∗a nếu n lẻ
Có thể cài đặt bằng đệ quy theo công thức trên hoặc cài khử đệ quy như sau:
int binpow(int a, int n) {
long long res = 1;
while (n > 0) {
if (n % 2 != 0) {
res = (res * a) % M;
}
a = ((long long)a * a) % M;
n /= 2;
}
return (int)res;
}
vector<int> n = getRepresentation(N);
vector<int> k = getRepresentation(K);
long long res = 1;
for (int i = 0; i < k.size(); ++i) {
res = (res * C(n[i], k[i])) % M;
}
Chúng ta thực hiện các bước như sau:
-
Phân tích thừa số nguyên tố M=m1a1.m2a2...mrar
-
Tính CNK mod m1, CNK mod m2,...CNK mod mr
-
Sử dụng Định lý Thặng dư Trung Hoa để khôi phục CNK mod M