hdu3073 Lucas定理

<span style="font-size:24px;">//在求形如C(n,k)%p这样的式子时，如果p值是一个可变的素数，
//而且不是特别大，就可以使用Lucas定理

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

long long pow_mod(long long a,long long i,long long p)
{
    if(i==0)return 1%p;
    long long temp=pow_mod(a,i>>1,p);
    temp=temp*temp%p;
    if(i&1)temp=temp*a%p;
    return temp;
}

long long Comb(long long a,long long b,long long p)
{
    if(a<b)return 0;
    if(a==b)return 1;
    if(b>a-b)b=a-b;
    long long ans=1,ca=1,cb=1;
    for(long long i=0;i<b;++i)
    {
        ca=(ca*(a-i))%p;
        cb=(cb*(b-i))%p;
    }
    ans=(ca*pow_mod(cb,p-2,p))%p;
    return ans;
}


long long Lucas(int n,int m,int p)
{
    long long ans=1;
    while(n!=0&&m!=0)
    {
        ans=(ans*Comb(n%p,m%p,p))%p;
        n/=p;
        m/=p;
    }
    return ans;
}

int main()
{
    int T,n,m,p;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&m,&p);
        printf("%lld\n",Lucas(n+m,m,p));//注意做法
    }
    return 0;
}
</span>