卢卡斯定理

前置技能

1. 乘法逆元
2. 组合数

公式

\(Lucas(a,b)=C(a\%p,b\%p)*Lucas(a/p,b/p)\%p\)

证明过程

这是信竞,记住就好,懒得写证明过程了(逃

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
int read(){
    int x=0,f=1;char c=getchar();
    while(c<'0'||c>'9')  f=(c=='-')?-1:1,c=getchar();
    while(c>='0'&&c<='9')  x=x*10+c-'0',c=getchar();
    return x*f;
}
int jc[100001];
void init(int p){
    jc[0]=jc[1]=1;
    for(int i=2;i<=100000;i++)
        jc[i]=jc[i-1]*i%p;
}
int inv(int a,int b,int p){
    int ans=1;
    while(b){
        if(b&1)
            ans=ans*a%p;
        a=a*a%p;
        b>>=1;
    }
    return ans;
}
int C(int x,int y,int p){
    if(y>x)
        return 0;
    return jc[x]%p*inv(jc[y]*jc[x-y],p-2,p)%p;
}
int Lucas(int x,int y,int p){
    if(y==0)
        return 1;
    return C(x%p,y%p,p)%p*Lucas(x/p,y/p,p)%p;
}
main(){
    int T=read(),p,x,y;
    while(T--)
        x=read(),y=read(),p=read(),init(p),printf("%lld\n",Lucas(x+y,y,p));
    return 0;
}