题目链接
题目大意
给你两个数n m
一共有2*n个桶
其中奇数桶（2*i-1） 每个桶可以拿ki个 球
偶数桶（2*i）每个桶可以拿x<=i个球
问你有多少种方案让你拿的球=m
这题要理解好题意
首先对于每个奇数桶k是可以不同的
其次对于相同的桶如果拿的球数量不同也看作是不同的方案
题目思路
一开始想过合并但是 由于一开始理解错了题意
误认为所有的k都是一样的 遂放弃了奇偶合并 转而去考虑合并奇数项和合并偶数项 百思不得其解
最终在题解的帮助下才知道k是可以不同的
那么就转而去考虑每个i的奇偶合并的可能性
对于每一个奇数项 选择的数字是ki 他的前一项选择的数字是i-x
合并这两项得到的是（k+1）*i -x (1<=x<=i-1 )
合并得到的新数字可以取任意的数 并且选择方案是唯一的
可能有人会问为什么要和前一项合并而不是和后一项
举个例子此时i=5 需要得到的值是10
假如和后一项合并 （k+1）*5-x (1<=x<=5 )
那么k=1 x=0 符合题意 k=2 x=5也符合题意 这样的计算方案不唯一
就导致了最终结果 出现偏差
因此要与前一项合并
我们令最后剩下的第n个偶数桶选了x个球
则之前的n个任意项要选择 m-x个
用插板法相当于 将m-x球放在n个位置每个位置不是必须要放
转化为 将 n-1块隔板放在m-x+n-1个空隙里（每个空隙都至少要放一个）
由于
将上面消项化简为
ans =
代码
#include <stdio.h>
#include <iostream>
#define MN 2000000
typedef long long ll;
using namespace std;
const int mod = 1000000007;
int n,m;
int fac[MN+5],inv[MN+5];ll qpow(ll bsc,ll y){ll ret = 1;while(y){if(y&1) ret = ret*bsc%mod;bsc = bsc*bsc%mod;y >>= 1; }return ret;
}void init(){fac[0] = 1;for(int i=1;i<=MN;i++)fac[i] = (ll)fac[i-1]*i%mod;inv[MN] = qpow(fac[MN],mod-2);for(int i=MN-1;i>=0;i--)inv[i] = (ll)inv[i+1]*(i+1)%mod;
}int C(int n,int m){if(m>n) return 0;return (ll)fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main()
{int t;init();cin>>t;while(t--){cin>>n>>m;int ans = C(m+n,n)-C(m-1,n);if(ans<0) ans += mod;printf("%d\n",ans);}return 0;
}