Link with balls

---

题目链接：VJ

---

Link with balls

题目描述

There were a lot of balls in the factory of Ball Illusion Technology(BIT). Link, a boy, went there to get some balls, but suddenly, he found that there were too many ways to get balls.

There are 2n buckets in the factory. Link may get kx balls from the 2x−1th bucket, where k is a non-negtive integer. He may also get at most x balls from the 2xth bucket.

Link wanted to get m balls, and he wondered how many ways there were to take out exactly m balls. While Link is calculating the answer, he wants you to calculate it as well, and you should output the answer modulo 10^9+7

输入：

The input consists of multiple test cases.

The first line contains an integer T (1 <= T <= 1e5) – the number of test cases.

Each test case contains two integers n and m (1 <= n, m <= 1e6)

输出：

For each test case, print the answer modulo 1e9+7 in a single line.

样例输入1

4
1 1
2 2
3 3
1000000 1000000

样例输出1

2
6
20
192151600

解释

题目的意思是一共有2n个篮子。第奇数(2x-1)个篮子可以拿kx个球，k为任意非负整数；第偶数(2x)个篮子可以拿[0,x]个球。问在这2n个篮子中拿取m个球有多少种情况，答案模1e9+7。

先考虑第一个篮子，1是奇数，也就是说我们在第一个篮子可以拿任意非负整数个球；那么之后的篮子呢？我们可以考虑将篮子合并，考虑第2个和第3个篮子。第2个篮子可以拿0,1个球，第3个篮子可以拿2k个球。那么把第2个篮子和第3个篮子加起来，也就是说，可以取2k个球或者2k+1个球，而k是非负整数，也就是说，第2个篮子和第3个篮子合并后也可以取任意个球。同样的，考虑第4个和第5个篮子，可以取3k,3k+1,3k+2个球，也是全体非负整数。由此推广，我们可以发现，第2n-2个和第2n-1个篮子，可以取kn+b,b∈[0,n-1],取遍全体非负整数。（不知为什么，写到这里，脑子突然想到了完全剩余系这个概念/doge）然后第2n个篮子单独拎出来。

第一步就这样完成了，经过合并，我们把2n个篮子分成了两部分。第一部分是n个可以取任意球的篮子，第二部分是只能取[0,n]个球的第n+1个篮子。我们的目的是找出在这n+1个篮子中取出m个球的方法数。

我们用组合数学的思维来思考问题。将第n+1个篮子中所取的球数从0到n开始枚举（先考虑m>=n)。假设第n+1个篮子中，我们取i个球，则我们剩下要取的球数就是m-i个球。我们的最终模型就变成了：对于每一个给定的i，在n个篮子，可以取[0,+∞)个球，要取m-i个球的方法数。

我们可以想到高中学过的隔板法。即 a1+a2+a3+a4+……+an=m-i 这一不定方程的正整数解的个数。略有区别的是，我们的球可以不取。为了适配隔板法，我们把初始球数均设为1，式子变成了 (a1-1)+(a2-1)+(a3-1)+……+(an-1)=m+n-i。我们用隔板法可以很快把式子写出来了:$C_{m+n-i-1}^{n-1}$。

第二步完成了。得到这个公式后，因为我们要将i从0到n代入并累加，并没有办法很快得到结果。我们要把公式进行转化。

这里有一个组合数公式。$C_{n}^{m}$=$C_{n-1}^{m}$+$C_{n-1}^{m-1}$。将我们得到的式子 $\sum_{i=0}^{n}$ $C_{m+n-i-1}^{n-1}$ 展开，即 $C_{m+n-1}^{n-1}$+$C_{m+n}^{n-1}$+……+$C_{m-1}^{n-1}$，然后先加上一个 $C_{m-1}^{n}$ ，和原来的式子一一合并，得到 $C_{m+n}^{n}$，然后减去之前加上的 $C_{m-1}^{n}$，就是最后我们用代码直接实现的公式。即 $C_{m+n}^{n}$-$C_{m-1}^{n}$。

第三步完成了。

代码部分还有需要注意的。当组合数出现不符合定义时，我们返回0，也刚好可以处理之前篮子数比所需取出的球数多的情况。由于数据较大，而且组合数中用到了除法，使用快速幂和逆元求解。关于快速幂和逆元，这里不再详细解释。

代码部分

#include<iostream>
using namespace std;
const int mod=1e9+7;
long long jc[2020000];
long long f(long long a,long long b)
{
	long long ans=1;
	while (b) {
		if (b&1) {
			ans=ans*a%mod;
		}
		a=a*a%mod;
		b>>=1;
	}
	return ans%mod;
}
long long c(long long a,long long b)
{
	if (a>b) return 0;
	return jc[b]*f(jc[a],mod-2)%mod*f(jc[b-a],mod-2)%mod;
}
int main()
{
	jc[0]=1;
	for (int i=1;i<=2000020;i++)
		jc[i]=jc[i-1]*i%mod;
	int t;
	scanf("%d",&t);
	while (t--) {	
		int n,m;
		scanf("%d%d",&n,&m);
		long long ans=c(n,m+n)-c(n,m-1)+mod;
		printf("%lld\n",ans%mod);
	}
	return 0;
}