Lucas定理

[图片上传失败...(image-139989-1517648456435)]
我们还能对

继续调用Lucas定理。

#include<cstdio>
using namespace std;
#define ll long long
int t;
ll A[100010];
ll kpow(ll a,int b,int p) {
    ll ans=1,now=a;
    int i=b;
    while(i){
        if(i%2==1) {
            ans=ans*now%p;
        }
        now=now*now%p;
        i=i>>1;
    }
    return ans;
}
ll C(int a,int b,int p) {
    if(a<b)return 0;
    else return ((A[a]*kpow(A[b],p-2,p))%p*kpow(A[a-b],p-2,p)%p);
}
ll lucas(int a,int b,int p) {
    if(!b)return 1;
    else return C(a%p,b%p,p)*lucas(a/p,b/p,p)%p;
}
int main() {
    scanf("%d",&t);
    while(t--) {
        int n,m,p;
        scanf("%d%d%d",&n,&m,&p);
        A[0]=1;
        for(int i=1; i<=p; i++)A[i]=(A[i-1]*i)%p;
        printf("%lld\n",lucas(n,m,p));
    }
    return 0;
}