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

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

题解：
问题可以转化成求方程 <nobr> x1+x2+……+xn=k </nobr>的非负整数解的个数,其中 <nobr> k=0 </nobr>~ <nobr> m </nobr>
利用插板法，构造 <nobr> yi=xi+1 </nobr>得到新的方程 <nobr> y1+y2+……+yn=n+k </nobr>的正整数解的个数是 <nobr> Cn−1n+k−1 </nobr>，即 <nobr> Ckn+k−1 </nobr>
所以现在问题转化为求 <nobr> ∑mi=0Cin+i−1 </nobr>，根据组合恒等式 <nobr> ∑ni=mCmi=Cm+1n+1 </nobr>（拿杨辉三角随便手玩一下就出来了），易得上式等于 <nobr> Cnn+m </nobr>
然后就转化为一个组合数取模的问题，题目中给出p是一个质数，所以直接Lucas就好了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define LL long long

LL 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一场空