【HDU3037】Saving Beans

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3037

题目大意：求在n棵树上摘不超过m颗豆子的方案，结果对p取模。

题解：
问题可以转化成求方程$x_1+x_2+……+x_n=k$的非负整数解的个数,其中$k=0$~$m$
利用插板法，构造$y_i=x_i+1$得到新的方程$y_1+y_2+……+y_n=n+k$的正整数解的个数是$C_{n+k-1}^{n-1}$，即$C_{n+k-1}^k$
所以现在问题转化为求$\sum _{i=0}^mC_{n+i-1}^i$，根据组合恒等式$\sum _{i=m}^nC_i^m=C_{n+1}^{m+1}$（拿杨辉三角随便手玩一下就出来了），易得上式等于$C_{n+m}^n$
然后就转化为一个组合数取模的问题，题目中给出p是一个质数，所以直接Lucas就好了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long longLL fac[100010];LL exgcd(LL a,LL b,LL &x,LL &y)
{if(!b){x=1;y=0;return a;}LL ret=exgcd(b,a%b,y,x);y-=a/b*x;return ret;
}LL Inv(LL a,LL mod)
{LL x,y;LL ret=exgcd(a,mod,x,y);if(ret==1) return (x%mod+mod)%mod;return -1;
}LL C(int n,int m,int mod)
{if(m>n) return 0;LL ret=fac[n];ret*=Inv((fac[m]*fac[n-m])%mod,mod);return ret%mod; 
}LL Lucas(LL n,LL m,LL mod)
{if(m==0) return 1;return C(n%mod,m%mod,mod)*Lucas(n/mod,m/mod,mod)%mod;
}int main()
{LL T,a,b,mod;fac[0]=1;scanf("%lld",&T);while(T--){scanf("%lld%lld%lld",&a,&b,&mod);for(int i=1;i<=mod;i++) fac[i]=(fac[i-1]*i)%mod;printf("%lld\n",Lucas(a+b,a,mod));}return 0;
}

ps：不开long long见祖宗，十年OI一场空