本文共 1573 字，大约阅读时间需要 5 分钟。

【引用自】

【一些常见的取值情况】

我们要解决的问题是 

• ，

ll C[1001][1001];void calc_Cmn(){     for(int i=0;i<1001;i++){        C[i][0]=C[i][i]=1;        for(int j=1;j

• ， 且 p 为素数
• 这里用到了Lucas定理

#include
    
     using namespace std;typedef long long LL;LL n,m,p;LL quick_mod(LL a, LL b){    LL ans=1;    a%=p;    while(b){        if(b&1){            ans=ans*a%p;            b--;        }        b>>=1;        a=a*a%p;    }    return ans;}LL C(LL n,LL m){    if(m>n) return 0;    LL ans=1;    for(int i=1;i<=m;i++){        LL a=(n+i-m)%p;        LL b=i%p;        ans=ans*(a*quick_mod(b,p-2)%p)%p;    }    return ans;}LL Lucas(LL n, LL m){    if(m==0) return 1;    return C(n%p,m%p)*Lucas(n/p,m/p)%p;}int main(){    int T; scanf("%d",&T);    while(T--){        scanf("%lld%lld%lld",&n,&m,&p);        printf("%lld\n", Lucas(n,m));    }    return 0;}
    

•  ， 且 p 有可能为合数
• 暴力分解+快速幂

#include
    
     using namespace std;typedef long long LL;const int N=200005;bool prime[N];int p[N];int cnt;void isprime(){    cnt=0;    memset(prime,true,sizeof(prime));    for(int i=2;i
     
      >=1;        a=a*a%m;    }    return ans;}LL Work(LL n,LL p){    LL ans=0;    while(n){        ans+=n/p;        n/=p;    }    return ans;}LL Solve(LL n,LL m,LL P){    LL ans=1;    for(int i=0;i
      
       <=n;i++){        LL x=Work(n,p[i]);        LL y=Work(n-m,p[i]);        LL z=Work(m,p[i]);        x-=(y+z);        ans*=quick_mod(p[i],x,P);        ans%=P;    }    return ans;}int main(){    isprime();    LL n,m,P;    while(~scanf("%lld%lld%lld",&n,&m,&P))        printf("%lld\n",Solve(n,m,P));    return 0;}
      
     
    

以上

转载地址：http://zhfen.baihongyu.com/