Lucas定理

Lucas定理一句话说就是
Lucas(m,n,p) = C$\tbinom{m/p}{n/p}$ * Lucas(m%p,n%p,p)

传送门

就是一道Lucas模板题

$C^m_n$ =${n!1/m!1/(n-m)!}$,而$1/m!$的逆元就是$m!$.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

ll p;
ll a[100000+5];

int T;

ll mod_pow(ll x,ll n,ll mod){       //快速幂
    ll res=1;
    while(n>0){
        if(n&1) res=res*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return res;
}

ll C(ll n,ll m){       //逆元求组合数
    if(m>n) return 0;
    return (a[n]*mod_pow(a[m],p-2,p))%p*mod_pow(a[n-m],p-2,p)%p;
}

ll Lucas(ll n,ll m)     //Lucas定理
{
    if(!m) return 1;
    else return C(n%p,m%p)*Lucas(n/p,m/p)%p;
}

int main(){
    scanf("%d",&T);
    while(T--)
    {
        ll n,m;
        scanf("%lld%lld%lld",&n,&m,&p);
        a[0]=1;
        for(int i=1;i<=p;i++) a[i]=(a[i-1]*i)%p;    //求i的阶乘.
        printf("%lld\n",Lucas(n+m,m));
    }
    return 0;
}