hdoj 3037 lucas定理+逆元

求c(n+m,m）公式很好推
Lucas 当mod为质数 Lucas(n,m,p)=cm(n%p,m%p)* Lucas(n/p,m/p,p)
Lucas(x,0,p)=1;

#include<cstdio>
#define LL long long
LL f[100005];
void init(LL n)
{
    f[0] = 1;
    for(int i=1;i<=n;i++)
    {
        f[i] = f[i-1]*i;
        f[i]%=n;
    }
}
int inv(LL i,int mod)
{
    if(i==1)return 1;
    else return inv((mod%i),mod)%mod*(mod-mod/i)%mod;
}
LL lucas(int n,int m,int mod)
{
      LL ans = 1;
      while(n&&m)
      {
          LL a = n%mod,b = m%mod;
          if(a<b)return 0;
          ans*=f[a]%mod*inv(f[b]*f[a-b]%mod,mod)%mod;
          ans%=mod;
          n/=mod;
          m/=mod;
      }
      return ans;
}
int main()
{
    int n,m,p,t;
    scanf("%d",&t);
    while(t--)
    {
       scanf("%d%d%d",&n,&m,&p);
       init(p);
       printf("%I64d\n",lucas(n+m,m,p));
    }
    return 0;
}