Link with Balls

给出 $2n$ 个箱子，可以从第 $2x-1$ 箱子取 $kx$ 个球，可以从第 $2x$ 箱子取至多 $x$ 个球，那么最终取 $m$ 个球有几种方法。

每 $n$ 个箱子是本质相同的，我们可以考虑使用生成函数进行计算。

设 $f_i(x) = \sum_{j = 0} ^ i x^j = \frac{1 - z^{i + 1}}{1 - z}$。

设 $g_i(x) = \sum_{j \ge 0} x^{i\times j} = \frac{1}{1 - x^i}$。

之后我们的答案就是 $\prod_{i = 1} ^ n f_i(x) \prod_{i = 1} ^ n g_i(x) = F(x)$。

$$
F(x) = \prod_{i = 1} ^ n \frac{1 - x^{i + 1}}{1 - x} \times \prod_{i = 1} ^ n \frac{1}{1 - x^i}
$$

仔细看看就会发现了左边的分子和右边下面是可以抵消的。

之后就会化成 $F(x) = \frac{1}{(1 - x)^{n + 1}} - \frac{x^n}{(1 - x) ^ {n + 1}}$。

之后直接二项式展开就行了。

发现答案就是 $[x^m]$ 也就是 $[x^m]F(x) = \binom{m + n}{m} - \binom{m - 1}{n}$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;
namespace Legendgod {
    namespace Read {
//        #define Fread
        #ifdef Fread
        const int Siz = (1 << 21) + 5;
        char *iS, *iT, buf[Siz];
        #define gc() ( iS == iT ? (iT = (iS = buf) + fread(buf, 1, Siz, stdin), iS == iT ? EOF : *iS ++) : *iS ++ )
        #define getchar gc
        #endif
        template <typename T>
        void r1(T &x) {
            x = 0;
            char c(getchar());
            int f(1);
            for(; !isdigit(c); c = getchar()) if(c == '-') f = -1;
            for(; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c ^ 48);
            x *= f;
        }
        template <typename T, typename...Args>
        void r1(T &x, Args&...arg) {
            r1(x), r1(arg...);
        }
        #undef getchar
    }

using namespace Read;

const int maxn = 2e6 + 5;
const int mod = 1e9 + 7;

int n, m;

int fac[maxn], finv[maxn];

int ksm(int x,int mi) {
    int res(1);
    while(mi) {
        if(mi & 1) res = 1ll * res * x % mod;
        mi >>= 1;
        x = 1ll * x * x % mod;
    }
    return res;
}

void init(int x) {
    fac[0] = 1;
    for(int i = 1; i <= x; ++ i) fac[i] = 1ll * fac[i - 1] * i % mod;
    finv[x] = ksm(fac[x], mod - 2);
    for(int i = x - 1; i >= 0; -- i) finv[i] = 1ll * finv[i + 1] * (i + 1) % mod;
}

int C(int n,int m) {
    if(n < 0 || m < 0 || n < m) return 0;
    return 1ll * fac[n] * finv[m] % mod * finv[n - m] % mod;
}

signed main() {
    int i, j, T;
    init(2e6);
    r1(T);
    while(T --) {
        r1(n, m);
        int ans = (C(n + m, m) - C(m - 1, n) + mod) % mod;
        printf("%d\n", ans);
    }
    return 0;
}

}


signed main() { return Legendgod::main(), 0; }