题目描述
(m)个猴子分(n)个桃，要求第一个猴子的桃数严格大于其他猴子，问有多少种分法对(1e9+7取模（\%1e9+7）)
Input
(1≤T≤25 ,1≤n,m≤100000)
第一行是(T),之后(T)行，输入(n)，(m)
Output
输出每组数据的分发数
Sample Input
2
2 2
3 5
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
",Ans);
}
}
signed main() {
_main();
return 0;
}