Saving Beans
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Now they turn to you for help, you should give them the answer. The result may be extremely huge; you should output the result modulo p, because squirrels can’t recognize large numbers.
Then followed T lines, each line contains three integers n, m, p, means that squirrels will save no more than m same beans in n different trees, 1 <= n, m <= 1000000000, 1 < p < 100000 and p is guaranteed to be a prime.
1 2 5
2 1 5
3
Hint
For sample 1, squirrels will put no more than 2 beans in one tree. Since trees are different, we can label them as 1, 2 … and so on.
The 3 ways are: put no beans, put 1 bean in tree 1 and put 2 beans in tree 1. For sample 2, the 3 ways are:
put no beans, put 1 bean in tree 1 and put 1 bean in tree 2.
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std; long long t,n,m,ans,p,f[],x,y; void exgcd(long long a,long long b){
if(b==){
x=; y=;
return;
}
exgcd(b,a%b);
long long t=x; x=y; y=t-(a/b)*y;
return;
} long long lucas(long long a,long long b,long long MOD){
long long res=;
while(a&&b){
long long aa=a%MOD,bb=b%MOD;
if(aa<bb) return ;
res=res*f[aa]%MOD;
exgcd(f[aa-bb]*f[bb],MOD);
x=(x%MOD+MOD)%MOD;
res=(res*x)%MOD;
a=a/MOD;
b=b/MOD;
}
return res;
} void init(long long MOD){
f[]=;
for(int i=;i<=MOD;i++){
f[i]=f[i-]*i%MOD;
}
} int main(){
scanf("%lld",&t);
for(int i=;i<=t;i++){
scanf("%lld%lld%lld",&n,&m,&p);
n=n+m;
init(p);
ans=lucas(n,m,p);
printf("%lld\n",ans);
}
}