题目:Sky 在玩一个神奇的游戏，这个游戏有n个互不相同的红色棋子和m 个互不相同黑色棋子，任意一个红色棋子都可以和任何一个黑色棋子抵消。Sky 会从这些棋子中选出若干个棋子，Sky想知道：有多少种选择的方案，可以使得 Sky 选择的棋子两两抵消。
先输入一个T，表示有T组。然后给定T组n，m。答案对1e9+7（考试的时候写成1e+7怒过样例，因为还有特判保留了20分的尊严)
\(1\le n,m,T\le 10^6\)
分析:一般人都能想到排列数吧，直接枚举选择棋子的数量，然后乘法原理。答案显然是
\[\sum ^{min(n,m)}_{i=1} C_n^i C_m^i
\]
先\(n^2\)预处理组合数表，每个询问\(O(n)\)计算上式即可。
但是这样显然不是正解，时空复杂度太大了。
进一步读题，我们可以发现棋子是可以放在一起拿的,没必要分成两堆挑。
假设我选出了i枚红棋，则我还要选i颗黑棋，也就是说，还有m-i颗黑棋没被选，那么就是说，选i颗红棋子，再选m-i颗黑棋表示不选。
这两个是等价的。
而上述第二种表述，其实就是在全部的棋子选出m颗棋子，i颗红棋，m-i个黑棋。因为不能什么都不选，答案还要减去1。
答案就是
\[C_{n+m}^m-1
\]
预处理阶乘，每个询问\(O(1)\)计算即可
#include<bits/stdc++.h>
#define rep(i,j,k) for(register int i(j);i<=k;++i)
#define drp(i,j,k) for(register int i(j);i>=k;--i)
using namespace std;
typedef long long lxl;
template<typename T>
inline T max(T &a, T &b) {
return a > b ? a : b;
}
template<typename T>
inline T min(T &a, T &b) {
return a < b ? a : b;
}
inline char gt() {
static char buf[1 << 21], *p1 = buf, *p2 = buf;
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++;
}
template <typename T>
inline void read(T &x) {
register char ch = gt();
x = 0;
int w(0);
while(!(ch >= ‘0‘ && ch <= ‘9‘))w |= ch == ‘-‘, ch = gt();
while(ch >= ‘0‘ && ch <= ‘9‘)x = x * 10 + (ch & 15), ch = gt();
w ? x = ~(x - 1) : x;
}
template <typename T>
inline void out(T x) {
if(x < 0) x = -x, putchar(‘-‘);
char ch[20];
int num(0);
while(x || !num) ch[++num] = x % 10 + ‘0‘, x /= 10;
while(num) putchar(ch[num--]);
putchar(‘\n‘);
}
const int mod = 1e9 + 7;
const int MX=2e6+79;
int n, m, k, tot;
lxl ans;
lxl fac[MX+111],inv_fac[MX+111];
inline lxl Quick_Pow(lxl a, lxl b,lxl mod) {
lxl res(1 % mod);
for(; b; b >>= 1) {
if(b & 1)
res = res * a % mod;
a = a * a % mod;
}
return res % mod;
}
inline lxl Fermat_inv(lxl a,lxl mod){
return Quick_Pow(a,mod-2,mod);
}
inline void calc() {
fac[0] = 1;//1??¨0!=1
int t=MX-5;
rep(i, 1, t)
fac[i] = (fac[i - 1] * i) % mod;
inv_fac[t] = Fermat_inv(fac[t], mod);
drp(i, t-1, 0)
inv_fac[i] = inv_fac[i + 1] * (i + 1) % mod;
}
inline lxl C(lxl r,lxl n){
if(n==0) return 1;
return fac[n]*inv_fac[r]%mod*inv_fac[n-r]%mod;
}
int main() {
freopen("chess.in", "r", stdin);
freopen("chess.out", "w", stdout);
int T;
calc();
read(T);
while(T--) {
read(n);
read(m);
if(m == 1) {
out(n);
continue;
}
ans =(( C(m,n+m) )%mod-1+mod)%mod;
out(ans);
}
return 0;
}