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 定理文章来源：https://www.toymoban.com/news/detail-624066.html
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("%lld\n",lucas(n+m,m)); } return 0; }
文章来源地址https://www.toymoban.com/news/detail-624066.html
到了这里，关于Lucas定理的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
![[电路]14-叠加定理和齐性定理](https://imgs.yssmx.com/Uploads/2024/02/455911-1.png)
