Nếu là số nguyên tố thì
Trong đó:
là dạng biểu diễn của trên hệ cơ số
là dạng biểu diễn của trên hệ cơ số
Nói cách khác:
Với là số nguyên tố và là số nguyên với
do
với mọi
Lại có:
và
Cứ tiếp tục như vậy, với mọi ta được:
Ta có:
(nhị thức Newton) (1)
Tách về dạng cơ số ta được:
(nhị thức Newton)
( với mọi và với ) (2)
Nhóm các lại ta có
Do đó với một bộ bất kì ta được một hạng tử
( là hệ số của )
Vậy
Từ đó suy ra: với mọi
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
Với nhỏ ta có thể sử dụng công thức tam giác Pascal để tính trước trong và truy vấn trong :
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 nhỏ các bạn có thể tiền xử lý trong và truy vấn trong 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 trong bằng chia để trị:
nếu chẵn
nếu 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ố
Tính , ,...
Sử dụng Định lý Thặng dư Trung Hoa để khôi phục