Cptraser/ 十月 28, 2018/ 2018.10/ 0 comments

Luogu模板题

    \[Lucas(n,m,p) = C_{n\mod p}^{m\mod p} * Lucas(n / p,m / p,p)\]

#include <cstdio>
using namespace std;

int N,M,P,T;
long long Inv[100005],Fac[100005];
long long Lucas(int x,int y){
    if(x<y)return 0;
    if(x<P)return Fac[x]*Inv[y]*Inv[x-y]%P;
    return Lucas(x%P,y%P)*Lucas(x/P,y/P)%P;
}
int main()
{
    for(scanf("%d",&T);T;T--){
        scanf("%d%d%d",&N,&M,&P);
        Fac[0]=Fac[1]=Inv[0]=Inv[1]=1;
        for(int i=2;i<=N+M;i++)Fac[i]=Fac[i-1]*i%P;
        for(int i=2;i<=N+M;i++)Inv[i]=(P-P/i)*Inv[P%i]%P;
        for(int i=2;i<=N+M;i++)Inv[i]=Inv[i-1]*Inv[i]%P;
        printf("%lld\n",Lucas(N+M,N));
    }
}
Share this Post

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*