考虑加多一颗树，这样的话当加的树放了k(0<=k<=m)个beans时，原本的n颗树上放的beans数量之和就等于m-k（<=m）,满足题目的要求 ，也降低了计算的难度。
则题目要求的是a1+a2+......an+an+1=m（0<=ai<=m,1<=i<=n+1) 式1
解有多少组。
考虑把问题转换成，求a1+a2+......an+an+1=m+n+1（1<=ai<=m+1,1<=i<=n+1) 式2
解有多少组。
因为式1的每组解，对于每个ai，都加上1的话，就是式2的一组解。
对于式2的求解：
考虑有m+n+1个Beans排成一列，则它们中恰好有m+n个间隔，在m+n个间隔中选择n个各插入一块木板，则把这些Beans分成n+1部分，每部分的值对应到每个ai，就是式2的一组解。而在m+n个间隔中选择n个，则是求组合数的问题了，p<=10^5且为质数，则可用Lucas定理求。
#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> using namespace std; typedef long long ll; ll n,m,p; ll POW(ll x,ll n,ll p){ ll res=1; while(n){ if(n&1)res=res*x%p; n>>=1; x=x*x%p; } return res; } ll cm(ll n,ll m,ll p){ ll a=1,b=1; while(m){ a=a*n%p; b=b*m%p; n--; m--; } return a*POW(b,p-2,p)%p; } ll lucas(ll n,ll m,ll p){ if(!m)return 1; return cm(n%p,m%p,p)*lucas(n/p,m/p,p)%p; } int main() { // freopen("in","r",stdin); int T; cin>>T; while(T--){ scanf("%I64d%I64d%I64d",&n,&m,&p); printf("%I64d\n",lucas(n+m,n,p)); } return 0; }
hdu 3037 Saving Beans (lucas定理)
原文：http://www.cnblogs.com/wshh/p/3988147.html