【HDU3037】Saving Beans

Lucas的裸题，学习一个。

#include<bits/stdc++.h>

#define N 100010

using namespace std;

typedef long long ll;

ll a[N];

int p;

ll pow(ll y,int z,int p){

    y%=p;ll ans=;

    for(int i=z;i;i>>=,y=y*y%p)if(i&)ans=ans*y%p;

    return ans;

}

ll C(ll n,ll m){

    if(m>n)return ;

    return ((a[n]*pow(a[m],p-,p))%p*pow(a[n-m],p-,p)%p);

}

ll Lucas(ll n,ll m){

    if(!m)return ;

    return C(n%p,m%p)*Lucas(n/p,m/p)%p;

}

inline int read(){

    int f=,x=;char ch;

    do{ch=getchar();if(ch=='-')f=-;}while(ch<''||ch>'');

    do{x=x*+ch-'';ch=getchar();}while(ch>=''&&ch<='');

    return f*x;

}

int main(){

    int T=read();

    while(T--){

        int n=read(),m=read();p=read();

        a[]=;

        for(int i=;i<=p;i++)a[i]=(a[i-]*i)%p;

        cout<<Lucas(n+m,n)<<endl;

    }

}