Lucas定理：
主要是求$C_{n}^{m}$在模$p$情况下($mod , p$)(一般$p$较小，而$n,m$较大的情况)
公式:
$ C_{n}^{m} ≡ C_{n , mod , p}^{m , mod , p} times C_{n/p}^{m/p} (mod , p) $
证明以后补吧
就以这题来说明具体解法：
题目
Luogu P3807 【模板】卢卡斯定理/Lucas 定理
Code:
//From:201929 #include<bits/stdc++.h> #define L long long using namespace std; L pq[100005]; L n,m,mod; L quick(L x,L y)//快速幂 { L ans=1; while(y) { if(y%2) ans=(ans*x)%mod; y>>=1; x=(x*x)%mod; } return ans; } L q(L x,L y) { if(y>x) return 0; return (pq[x]*quick(pq[y],mod-2))%mod*quick(pq[x-y],mod-2)%mod; //pq[x]/pq[y]/pq[x-y] //逆元变成pq[x]*(pq[y]^(mod-2))*(pq[x-y]^(mod-2)) //暴力求解C x,y的值 } L lucas(L x,L y) { if(y==0) return 1ll; return (lucas(x/mod,y/mod)*q(x%mod,y%mod))%mod; } int main() { int t; scanf("%d",&t); while(t--) { scanf("%lld%lld%lld",&n,&m,&mod); pq[0]=1; for(int i=1;i<=mod;i++) pq[i]=(pq[i-1]*i)%mod; //预处理小情况（x<mod）的答案 printf("%lldn",lucas(n+m,m)); } return 0; }
内容来源于网络如有侵权请私信删除
文章来源: 博客园
- 还没有人评论，欢迎说说您的想法！
客服
