Saving Beans
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2079 Accepted Submission(s): 748
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.
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<iostream>
#include<stdio.h>
#include<cstring>
#include<cstdlib>
#include<vector>
using namespace std;
typedef __int64 LL; LL dp[]; void init(LL p){
int i;
dp[]=;
for(i=;i<=p;i++)
dp[i]=(dp[i-]*i)%p;
}
LL pow_mod(LL a,LL n,LL p)
{
LL ans=;
while(n)
{
if(n&) ans=(ans*a)%p;
n=n>>;
a=(a*a)%p;
}
return ans;
}
LL C(LL a,LL b,LL p)
{
if(a<b) return ;
if(b>a-b) b=a-b;
LL sum1=dp[a];
LL sum2=(dp[b]*dp[a-b])%p;
sum1=(sum1*pow_mod(sum2,p-,p));
return sum1;
}
LL Lucas(LL n,LL m,LL p)
{
LL ans=;
while(n&&m&&ans)
{
ans=(ans*C(n%p,m%p,p))%p;
n=n/p;
m=m/p;
}
return ans;
}
int main()
{
int T;
LL n,m,p;
scanf("%d",&T);
while(T--)
{
scanf("%I64d%I64d%I64d",&n,&m,&p);
init(p);
if(n>m)swap(n,m);
LL ans= Lucas(n+m,m,p);
printf("%I64d\n",ans);
}
return ;
}