http://acm.hdu.edu.cn/showproblem.php?pid=3037

 

枚举Beans的数量x∈[0,m]，然后用隔板法，答案就是Σ C(n+x-1,n-1),x∈[0,m]

但是直接这么算会超时，需要变化化简。

C(n-1,n-1)+C(n,n-1)+C(n+1,n-1)+...+C(n+m-1,n-1)

=C(n-1,0)+C(n,1)+C(n+1,2)+...+C(n+m-1,m)

=C(n,0)+C(n,1)+C(n+1,2)+...+C(n+m-1,m)

=C(n+m,m)

然后卢卡斯，费马小定理就行了，注意mod是1e5，1e5*1e5会溢出int。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
int t,n,m,p;
ll ans;

int pow_mod(int a,int n,int m)
{	
	if(!n)return 1;
	int x=pow_mod(a,n/2,m);
	ll ans=(ll)x*x%m;
	if(n&1)ans=ans*a%m;
	return (int)ans;
}

int inv(int a){return pow_mod(a,p-2,p);}

int C(int n,int m)
{
	if(m>n)return 0;
	ll facn=1,facm=1,facn_m=1;
	for(int i=1;i<=n;i++)facn=facn*i%p;
	for(int i=1;i<=m;i++)facm=facm*i%p;
	for(int i=1;i<=n-m;i++)facn_m=facn_m*i%p;
	return (ll)facn*inv(facm)%p*inv(facn_m)%p;
}

int Lucas(int n,int m)
{
	if(m==0)return 1;
	return (long long)C(n%p,m%p)*Lucas(n/p,m/p)%p;
}

int main()
{
//	freopen("input.in","r",stdin);
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d%d",&n,&m,&p);
		cout<<Lucas(n+m,m)<<endl;
	}
	return 0;
}