hdu_5201 The Monkey King

题目:

  As everyone known, The Monkey King is Son Goku. He and his offspring live in Mountain of Flowers and Fruits. One day, his sons get n peaches. And there are m monkeys (including GoKu), they are numbered from 1 to m, GoKu’s number is 1. GoKu wants to distribute these peaches to themselves. Since GoKu is the King, so he must get the most peach. GoKu wants to know how many different ways he can distribute these peaches. For example n=2, m=3, there is only one way to distribute these peach: 2 0 0.
  When given n and m, you are expected to calculate how many different ways GoKu can distribute these peaches. Answer may be very large, output the answer modular instead.

思路:

  如果个猴子分个桃,可以为零。由隔板法和可重组合可得到方案数为
  设猴王最后得到的桃子数为,那么我们可以先钦定个猴子超过猴王。剩下的桃子就随意分配(不给猴王就行了),这样就能得到至少个猴得到桃数超过猴王的方案数:
  
  但是这样计算会重复。当实际有个猴超过了猴王,我们钦定了个猴时这个方案被计算了
  那么我们把这些式子全部列在一起(为实际有个超过猴王,为猴王的桃数):
  
  
  
  
  对二项式展开可以得到,
  所以把这些式子竖下来偶加奇减,最后得到的就是
  
  只要再枚举一个就好了。
  复杂度看起来像是,不过应该是比这个小很多的:
  复杂度为,这个表达式的增长与接近。

代码:

#include <bits/stdc++.h>
#define MN 100005
using namespace std;
typedef long long ll;
const int MOD=1e9+7;
void exgcd(ll a,ll b,ll &x,ll &y){
    if(!b){x=1;y=0;return;}
    exgcd(b,a%b,y,x);y-=a/b*x;
}
int inv(int a){
    ll x,y;
    exgcd(a,MOD,x,y);
    return (x%MOD+MOD)%MOD;
}
int fac[MN<<1],invfac[MN<<1];
void init(){
    int n=200000;
    fac[0]=1;
    for(int i=1;i<=n;i++)
        fac[i]=(ll)fac[i-1]*i%MOD;
    invfac[n]=inv(fac[n]);
    for(int i=n-1;i>=0;i--)
        invfac[i]=(ll)invfac[i+1]*(i+1)%MOD;
}
int C(int x,int y){
    return (ll)fac[x]*invfac[x-y]%MOD*invfac[y]%MOD;
}
int H(int x,int y){
    return C(x+y-1,y);
}
int main(){
    init();
    int cas,n,m;
    scanf("%d",&cas);
    while(cas--){
        scanf("%d%d",&n,&m);
        if(m==1){
            puts("1");
            continue;
        }
        int ans=0;
        for(int x=1;x<=n;x++){
            for(int p=0;p<m;p++){
                int l=n-x*(p+1);
                if(l<0)break;
                int tmp=(ll)C(m-1,p)*H(l+1,m-2)%MOD;
                (ans+=(p&1?-1:1)*tmp)%=MOD;
            }
        }
        printf("%d\n",(ans+MOD)%MOD);
    }
    return 0;
}