题意：给你n对桶，第i对能分别提供出来0,1,2,…,i-1个球以及0,i,2i,3i,…个球，问凑m个球的方案数
第i对的生成函数为
[m (1+x+x^2+…+x^i)(1+x^i+x^{2i}+…)
]
]
等比数列求和有
[dfrac{x^{i+1}-1}{x-1} imes dfrac{1}{1-x^i}
]
]
考虑生成函数的实际意义，把n个生成函数乘起来，答案就是(x^m)的系数
[prodlimits_{i=2}^{n+1}dfrac{x^i-1}{x-1}prodlimits_{i=1}^{n}{dfrac{1}{1-x^i}}
]
]
抽出来前面的n+1项和后面的第1项，有
[dfrac{x^{n+1}-1}{x-1} imes dfrac{1}{x-1}(-1)^nprodlimits_{i=2}^{n}dfrac{x^i-1}{x-1}dfrac{1}{x^i-1}
]
]
后面都被干掉了，把下面的1+1+(n-1)个(x-1)合并起来有
[(-1)^ndfrac{x^{n+1}-1}{(x-1)^{n+1}}
]
]
把分母用广义二项式定理展开有
[(-1)^n(x^{n+1}-1)sumlimits_{k=0}^infty mathbf{C}_{-(n+1)}^{k}(-1)^kx^k(-1)^{-(n+1)-k}
]
]
对组合数做负指标变换
[(-1)^n(x^{n+1}-1)sumlimits_{k=0}^infty mathbf{C}_{k+(n+1)-1}^{k}(-1)^kx^k(-1)^{-(n+1)-k}
]
]
合并一下(-1)的指数，发现能提出来，和前面的合并
[(1-x^{n+1})sumlimits_{k=0}^infty mathbf{C}_{k+n}^kx^k
]
]
至此可以做了，我们要找(x^m)的系数
首先令k=m，得到(mathbf{C}_{m+n}^m)
然后令k=m-(n+1)，得到(-mathbf{C}_{m-1}^{m-(n+1)})，也即(-mathbf{C}_{m-1}^{n})
注意前面有个负号
最终答案为(mathbf{C}_{m+n}^m – mathbf{C}_{m-1}^n)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 1e9+7;
const int MAXN = 2000006;
int fac[MAXN];
int inv[MAXN];
int qpow(int x,int y=MOD-2){
int ret=1,base=x;
while(y){
if(y&1) ret=ret*base%MOD;
base=base*base%MOD;
y>>=1;
}
return ret;
}
int c(int x,int y){
if(x<y) return 0;
return fac[x]*inv[y]%MOD*inv[x-y]%MOD;
}
signed main(){
fac[0]=1;
for(int i=1;i<=2000000;i++)
fac[i]=fac[i-1]*i%MOD;
inv[2000000]=qpow(fac[2000000]);
for(int i=2000000-1;i>=1;i--)
inv[i]=inv[i+1]*(i+1)%MOD;
int T;
cin>>T;
while(T--){
int n,m;
cin>>n>>m;
cout<<(c(n+m,m)-c(m-1,n)+MOD)%MOD<<endl;
}
}