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<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;
}