这是一道模板题。
给定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:
2
1 2 5
2 1 5
输出样例#1:
3
3
卢卡斯定理
$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("%lld\n",Lucas(n+m,m,mod)%mod);
46 }
47 return 0;
48 }