传送门

题意

有 ​​ 个篮子，编号为 ​，每个篮子里面有无限多球，现在要从这些篮子里面取出 个球，问取出球的方案数有多少种。（当每种方案中，有一个篮子的取球数不同，则看作为是不同方案）

一些取球的限定条件：在第 ​​ 个篮子中只能取 ​​ 个球，在第 ​​ 个篮子中最多取 ​​ 个球

思路

官方题解 ↓

观察取球的限制很容易想到将奇偶分开讨论，再套用生成函数，将取球方式表示出来即可

先考虑篮子编号为偶数的情况：

一共有 个偶数篮子，在这里对应的编号为 ，对编号为 的偶数篮子，能取出的球为 个，对应的写成生成函数为
先考虑篮子编号为奇数的情况：

一共有 个奇数篮子，在这里对应的编号为 ，对编号为 的奇数篮子，能取出的球为 个，（这里题面没有说清楚，实际上，每个 的取值相互独立），对应的写成生成函数为
注：累乘的每一项表示的是对编号为 ​ 的篮子取出多少个球来进行讨论的，而对奇数篮子每个篮子取出的球都是 的整数倍，需要枚举 的倍数。

有个推论

转侵删

化简后的公式为
可以求出 ​​ 的系数为 ​

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int ll
#define rep(i, j, k) for (ll(i) = (j); (i) <= (k); (++i))
#define rrep(i, j, k) for (ll i = (ll)(j); i >= (ll)(k); i--)
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e6 + 7;
ll fac[N + 10], facInv[N + 10];
ll qkpow(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1)
            ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
ll getInv(ll a) { return qkpow(a, mod - 2); }
void init() {
    fac[0] = 1;
    rep(i, 1, N) fac[i] = fac[i - 1] * i % mod;

    facInv[N] = getInv(fac[N]);
    rrep(i, N - 1, 0) facInv[i] = facInv[i + 1] * (i + 1) % mod;
}
ll C(int n, int m) {
    if (m < 0 || m > n)
        return 0;
    return (fac[n] * facInv[m] % mod) * facInv[n - m] % mod;
}
void solve() {
    int n, m;
    scanf("%lld%lld", &n, &m);
    int ans = (C(m + n, n) - C(m - 1, m - n - 1) + mod) % mod;
    printf("%d\n", ans);
}
signed main() {
    init();
    int t;
    scanf("%lld", &t);
    while (t--)
        solve();
    return 0;
}