题目背景
这是一道模板题。
题目描述
给定n,m,p(1le n,m,ple 10^51≤n,m,p≤105)
求 C_{n+m}^{m} mod pCn+mm mod p
保证P为prime
C表示组合数。
一个测试点内包含多组数据。
输入输出格式
输入格式：
第一行一个整数T(Tle 10T≤10)，表示数据组数
第二行开始共T行，每行三个数n m p，意义如上
输出格式：
共T行，每行一个整数表示答案。
输入输出样例
卢卡斯定理
$C(n,m) % p = C(n % p, m % p) * C(n / p, m / p)$
对于这道题来说，p是素数，解逆元的时候用快速幂
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<algorithm> 5 #define LL long long 6 using namespace std; 7 const LL MAXN=1e6+10; 8 const LL INF=0x7fffff; 9 inline LL read() 10 { 11 char c=getchar();LL flag=1,x=0; 12 while(c<'0'||c>'9') {if(c=='-') flag=-1;c=getchar();} 13 while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*flag; 14 } 15 LL js[MAXN]; 16 LL fastpow(LL a,LL p,LL mod) 17 { 18 LL base=1; 19 while(p) 20 { 21 if(p&1) base=(base*a)%mod; 22 a=(a*a)%mod; 23 p>>=1; 24 } 25 return base; 26 } 27 LL C(LL n,LL m,LL mod) 28 { 29 if(m>n) return 0; 30 return js[n]*fastpow(js[m],mod-2,mod)*fastpow(js[n-m],mod-2,mod)%mod; 31 } 32 LL Lucas(LL n,LL m,LL mod) 33 { 34 if(m==0) return 1; 35 else return C(n%mod,m%mod,mod)*(Lucas(n/mod,m/mod,mod))%mod; 36 } 37 int main() 38 { 39 LL T=read(); 40 js[0]=1; 41 while(T--) 42 { 43 LL n=read(),m=read(),mod=read(); 44 for(LL i=1;i<=mod;i++) js[i]=(js[i-1]*i)%mod; 45 printf("%lldn",Lucas(n+m,m,mod)%mod); 46 } 47 return 0; 48 }
内容来源于网络如有侵权请私信删除
- 还没有人评论，欢迎说说您的想法！
客服
