Nếu M là số nguyên tố thì CNK≡Cn0k0×Cn1k1⋯Cnpkp(modM)
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(modM) do gcd(M,i!)=1
⇒(1+X)M=∑i=0MCMi×Xi≡1+XM(modM) với mọi X∈Z
Lại có:
(1+XM)M≡((1+X)M)M≡(1+X)M2(modM)
và
(1+XM)M≡1+(XM)M≡1+XM2(modM)
⇒(1+X)M2≡1+XM2(modM)
Cứ tiếp tục như vậy, với mọi i∈N ta được:
(1+X)Mi≡1+XMi(modM)
Ta có:
K=0∑NCNK×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=0∏p((1+X)Mi)ni
≡i=0∏p(1+XMi)ni(modM)
=∏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(modM) với mọi X∈Z
⇔CNK≡i=0∏pCniki(modM)
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=(a2n)2 nếu n chẵn
an=(a2n)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 CNKmodm1, CNKmodm2,...CNKmodmr
-
Sử dụng Định lý Thặng dư Trung Hoa để khôi phục CNKmodM