Lucas定理

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#define L long longusing 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;}