洛谷—— P3807 【模板】卢卡斯定理

https://www.luogu.org/problemnew/show/3807

题目背景

这是一道模板题。

题目描述

给定n,m,p(1\le n,m,p\le 10^51≤n,m,p≤105)

求 C_{n+m}^{m}\ mod\ pCn+mm mod p

保证P为prime

C表示组合数。

一个测试点内包含多组数据。

输入输出格式

输入格式：

第一行一个整数T(T\le 10T≤10)，表示数据组数

第二行开始共T行，每行三个数n m p，意义如上

输出格式：

共T行，每行一个整数表示答案。

输入输出样例

输入样例#1：复制

输出样例#1：复制

3

3

 #include <cstdio>

 #define LL long long

 inline void read(int &x)

 {

     x=; register char ch=getchar();

     for(; ch>''||ch<''; ) ch=getchar();

     for(; ch>=''&&ch<=''; ch=getchar()) x=x*+ch-'';

 }

 const int N(1e5+);

 LL fac[N];

 inline LL Pow(LL a,int b,int p)

 {

     LL ret=;

     for(; b; b>>=,a*=1ll*a,a%=p)

         if(b&) ret*=1ll*a,ret%=p;

     return ret;

 }

 inline LL C(LL n,LL m,LL p)

 {

     if(n<m) return ;

     return fac[n]%p*Pow(fac[m],p-,p)%p*Pow(fac[n-m],p-,p)%p;

 }

 inline LL lus(LL n,LL m,LL p)

 {

     if(m==) return ;

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

 }

 int Presist()

 {

     int t; read(t); fac[]=;

     for(int n,m,p; t--; )

     {

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

         for(int i=; i<=n+m; ++i)

             fac[i]=1ll*fac[i-]%p*i%p;

         printf("%lld\n",lus(n+m,m,p));

     }

     return ;

 }

 int Aptal=Presist();

 int main(int argc,char**argv){;}

巴特西