Saving Beans
Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4315 Accepted Submission(s): 1687
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.
裸的lucas定理，直接调用函数即可。
我暂时不明白为什么是C((n+m),m)，以后再研究吧。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std; typedef long long ll; ll quick_mod(ll a,ll b,ll m){
ll ans = ;
a %= m;
while(b){
if(b&)
ans = ans * a % m;
b >>= ;
a = a * a % m;
}
return ans;
} ll getC(ll n, ll m,ll mod){
if(m > n)
return ;
if(m > n-m)
m = n-m;
ll a = ,b = ;
while(m){
a = (a*n)%mod;
b = (b*m)%mod;
m--;
n--;
}
return a*quick_mod(b,mod-,mod)%mod;
} ll Lucas(ll n,ll k,ll mod){
if(k == )
return ;
return getC(n%mod,k%mod,mod)*Lucas(n/mod,k/mod,mod)%mod;
} int main(){
int T;
scanf("%d",&T);
while(T--){
ll n,m,mod;
scanf("%lld%lld%lld",&n,&m,&mod);
printf("%lld\n",Lucas(n+m,m,mod));
}
return ;
}