【hdu多校 7047】Link with Balls

传送门

题意

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

一些取球的限定条件：在第 $2x-1$ 个篮子中只能取 $kx$ 个球，在第 $2x$ 个篮子中最多取 $x$ 个球

思路

官方题解 ↓

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

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

一共有 $n$ 个偶数篮子，在这里对应的编号为 $1\sim n$ ，对编号为 $i$ 的偶数篮子，能取出的球为 $num\leq i$ 个，对应的写成生成函数为 $f_{even}=\prod_{i=1}^{n} (1+x+x^2+...+x^i)=\prod_{i=1}^{n} \frac{1-x^{i+1}}{1-x}$
先考虑篮子编号为奇数的情况：

一共有 $n$ 个奇数篮子，在这里对应的编号为 $1\sim n$ ，对编号为 $i$ 的奇数篮子，能取出的球为 $num=k*i$ 个，（这里题面没有说清楚，实际上，每个 $k$ 的取值相互独立），对应的写成生成函数为 $f_{odd}=\prod_{i=1}^{n}\sum_{k=0}^{\infty}x^{ki}=\prod_{i=1}^{n}(1+x^i+x^{2i}+...)=\prod_{i=1}^{n}\frac{1}{1-x^i}$
注：累乘的每一项表示的是对编号为 $i$ 的篮子取出多少个球来进行讨论的，而对奇数篮子每个篮子取出的球都是 $k$ 的整数倍，需要枚举 $k$ 的倍数。

有个推论

图片说明
转侵删

$f_{odd}*f_{even}$ 化简后的公式为 $\frac{1-x^{n+1}}{(1-x)^{n+1}}=(1-x^{n+1})\sum_{i}^{\infty}C_{n+i}^{i}x^i$
可以求出 $x^m$ 的系数为 $C_{n+m}^{n}-C_{m-1}^{m-n-1}$

#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;
}