HDU-5201 The Monkey King

题目描述

\(m\)个猴子分\(n\)个桃，要求第一个猴子的桃数严格大于其他猴子，问有多少种分法对\(1e9+7取模（\%1e9+7）\)

Input

\(1≤T≤25 ,1≤n,m≤100000\)

第一行是\(T\),之后\(T\)行，输入\(n\)，\(m\)

Output

输出每组数据的分发数

Sample Input

Sample Output

1

5

先来看一下基础的版本，即\(m\)个猴子分\(n\)个桃子，这我们可以利用隔板法解决，

答案就是\(C(m+n-1,m)\);

现在，我们加入了限制条件，第一只猴子数量大于等于其他猴子的数量。

我们发现\(n\)实际上并不是很大，于是便很容易想到通过枚举第一只猴子拿桃子的数量进行求解。

对于我们当前枚举猴子拿的桃子的数量\(x\)，我们再枚举拿桃子数量何其相同的猴子的数量。

我们定义:\(F(i,j)\)表示\(i\)个猴子分\(j\)个桃子的方案数。

假设，当前至少有\(i\)只猴子拿桃子的数量大于等于第一只的数量，让我们来计算方案数。

第一只猴子拿完后还剩\(n-x\)个桃子，有\(i\)只猴子拿至少\(x\)个，剩下\(n-x-i*x\)个桃子分给\(m-1\)个猴子。

即\(F(m-1,n-(i+1)*x)\)，当\(n<(i+1)*x\)时\(return\)掉。

由于我们求出的是至少\(i\)只猴子的数量大于等于第一只的方案数，那么我们就可以容斥求解。

\(Ans=\)至少\(0\)只猴子的数量-至少\(1\)只猴子的数量+至少\(2\)只猴子的数量.....-至少\(n\)只猴子的数量.

同时，我们需要注意的是若\(m-1\)个猴子分\(n-x\)个桃子每只猴子分到的桃子数量已经\(>=x\)了，

那么说明无论怎样第一只猴子都不会是最多的(即\(x<=(n-x+m-2)/(m-1)\))就要\(return\)掉。

代码如下

#include <bits/stdc++.h>

using namespace std;

#define int long long

#define reg register

#define clr(a,b) memset(a,b,sizeof a)

#define Raed Read

#define Mod(x) (x>=mod)&&(x-=mod)

#define debug(x) cerr<<#x<<" = "<<x<<endl;

#define rep(a,b,c) for(reg int a=(b),a##_end_=(c); a<=a##_end_; ++a)

#define ret(a,b,c) for(reg int a=(b),a##_end_=(c); a<a##_end_; ++a)

#define drep(a,b,c) for(reg int a=(b),a##_end_=(c); a>=a##_end_; --a)

#define erep(i,G,x) for(int i=(G).Head[x]; i; i=(G).Nxt[i])

inline int Read(void) {

	int res=0,f=1;

	char c;

	while(c=getchar(),c<48||c>57)if(c=='-')f=0;

	do res=(res<<3)+(res<<1)+(c^48);

	while(c=getchar(),c>=48&&c<=57);

	return f?res:-res;

}

template<class T>inline bool Min(T &a, T const&b) {

	return a > b ? a = b, 1 : 0;

}

template<class T>inline bool Max(T &a, T const&b) {

	return a < b ? a = b, 1 : 0;

}

const int N=2e5+5,M=6005,mod=1e9+7;

bool MOP1;

int Fac[N];

inline int Pow(int x,int y) {

	int res=1;

	while(y) {

		if(y&1)res=(res*x)%mod;

		x=(x*x)%mod,y>>=1;

	}

	return res;

}

inline int C(int x,int y) {

	return Fac[x]*Pow(Fac[x-y]*Fac[y]%mod,mod-2)%mod;

}

inline int F(int x,int y) {

	return C(x+y-1,x);

}

bool MOP2;

inline void _main() {

	Fac[0]=1;

	ret(i,1,N)Fac[i]=(Fac[i-1]*i)%mod;

	int T=Read();

	while(T--) {

		int n=Read(),m=Read(),Ans=0;

		if(n==1||m==1) {

			puts("1");

			continue;

		}

		rep(x,1,n) {

			int Ma=(n-x+m-2)/(m-1);

			if(x<=Ma)continue;

			rep(i,0,n) {

				if(n<(i+1)*x)break;

				int res=C(m-1,i)*F(n-(i+1)*x,m-1)%mod;

				if(i&1)Ans-=res-mod;

				else Ans+=res;

				Mod(Ans);

			}

		}

		printf("%lld\n",Ans);

	}

}

signed main() {

	_main();

	return 0;

}

巴特西