拓展Lucas定理解决大组合数取模并且模数为任意数的情况
大概的思路是把模数用唯一分解定理拆开之后然后去做
然后要解决的一个子问题是求模质数的k次方
将分母部分转化成逆元再去做就好了
#include<bits/stdc++.h>
using namespace std;
const int maxn = + ;
typedef long long LL; LL Pow(LL n, LL m, LL mod) {
LL ans = ;
while(m > ) {
if(m & ) ans = (LL)ans * n % mod;
n = (LL)n * n % mod; m >>= ;
}
return ans;
}
LL Pow(LL n,LL m) {
LL ans = ;
while(m > ) {
if(m & ) ans = ans * n;
n = n * n; m >>= ;
}
return ans;
}
LL x, y;
LL exgcd(LL a, LL b) {
if(a == ) {
x = , y = ;
return b;
}LL r = exgcd(b%a, a);
LL t = x; x = y - (b/a)*x; y = t;
return r;
}
LL rev(LL a, LL b) { exgcd(a, b); return ((x % b) + b) % b; }
LL Calc(LL n, LL p, LL t) {
if(n == ) return ; LL s = Pow(p, t), k = n / s, tmp = ;
for(LL i=; i<=s; i++) if(i % p) tmp = (LL)tmp * i % s; LL ans = Pow(tmp, k, s);
for(LL i=s*k + ; i<=n; i++) if(i % p) ans = (LL)ans * i % s; return (LL)ans * Calc(n / p, p, t) % s;
}
LL C(LL n, LL m, LL p, LL t) {
LL s = Pow(p, t), q = ;
for(LL i=n; i; i/=p) q += i / p;
for(LL i=m; i; i/=p) q -= i / p;
for(LL i=n-m; i; i/=p) q -= i / p; LL ans = Pow(p, q);
LL a = Calc(n, p, t), b = Calc(m, p, t), c = Calc(n-m, p, t);
return (LL)(ans * a * rev(b, s) * rev(c, s)) % s;
}
LL China(LL A[], LL M[], LL cnt) {
LL ans = , m, n = ;
for(LL i=; i<=cnt; i++) n *= M[i];
for(LL i=; i<=cnt; i++) {
m = n / M[i];
exgcd(M[i], m);
ans = (ans + (LL)y * m * A[i]) % n;
}
return (ans + n) % n;
}
LL A[maxn], M[maxn], cnt;
LL Lucas(LL n, LL m, LL mod) {
for(LL i=; i*i <= mod; i++) if(mod % i == ) {
LL t = ;
while(mod % i == ) t++, mod /= i;
M[++cnt] = Pow(i, t);
A[cnt] = C(n, m, i, t);
}if(mod > ) {
M[++cnt] = mod;
A[cnt] = C(n, m, mod, );
}
return China(A, M, cnt);
}
LL n, k, p;
int main() {
cin >> n >> k >> p;
cout << Lucas(n, k, p) << endl;
return ;
}
然后补充一个内容，线性时间复杂度内求出所有的逆元
A[i] = -(p / i) * A[p % i];