二项式反演

定义

直接给出式子：

\[ g_i=\sum_{k\geqslant i}\binom ki f_k \rightarrow f_i=\sum_{k\geqslant i}\binom ki (-1)^{k-i}g_k \]

看起来不知道咋用？待会再说，我们先证明。

证明

前置知识

组合数学常用记号

二项式定理

正文

已知：\(g_i=\sum_{k\geqslant i}\binom ki f_k\)
求证：\(f_i=\sum_{k\geqslant i}\binom ki (-1)^{k-i}g_k\)

把求证右边那个式子单独拿出来，想办法把它导成 \(f_i\)。

\[ \begin{aligned} &\sum_{k\geqslant i}\binom ki (-1)^{k-i}g_k \newline =&\sum_{k\geqslant i}\binom ki (-1)^{k-i} \sum_{j\geqslant k}\binom jk f_j \end{aligned} \]

把第二个求和号以及 \(f_j\) 挪动一下，感性理解一下，发现最后每一项出现的次数还是不变的，所以正确。

\[ \begin{aligned} &\sum_{k\geqslant i}\binom ki (-1)^{k-i} \sum_{j\geqslant k}\binom jk f_j \newline =&\sum_{j\geqslant i}f_j \sum_{j\geqslant k \geqslant i}\binom jk \binom ki (-1)^{k-i} \newline =&\sum_{j\geqslant i}f_j \sum_{j\geqslant k \geqslant i}\frac{j!k!}{k!(j-k)!i!(k-i)!} (-1)^{k-i} \newline =&\sum_{j\geqslant i}f_j\frac{j!}{i!}\sum_{j\geqslant k \geqslant i}\frac 1{(j-k)!(k-i)!} (-1)^{k-i} \end{aligned} \]

展开之后不知道怎么往下算了，想办法把那个大分式化成点什么，比如二项式（组合数）。

上下同乘 \((j-i)!\)，然后 \((j-k)=[(j-i)-(k-i)]\)，然后就可以轻松化成组合数形式继续往下导公式了。

\[ \begin{aligned} &\sum_{j\geqslant i}f_j\frac{j!}{i!} \sum_{j\geqslant k \geqslant i}\frac 1{(j-k)!(k-i)!} (-1)^{k-i} \newline =&\sum_{j\geqslant i}f_j\frac{j!}{i!} \sum_{j\geqslant k \geqslant i}\frac {(j-i)!}{[(j-i)-(k-i)]!(k-i)!(j-i)!} (-1)^{k-i} \newline =&\sum_{j\geqslant i}f_j\frac{j!}{i!} \sum_{j\geqslant k \geqslant i}\frac {\binom{j-i}{k-i}}{(j-i)!} (-1)^{k-i} \newline \end{aligned} \]

换个形式

\[ \sum_{j\geqslant i}f_j\frac{j!}{i!} \cdot \frac{\sum_{j\geqslant k \geqslant i } \binom{j-i}{k-i} (-1)^{k-i}}{(j-i)!} \]

大分式上面的分母可以用 二项式定理 处理掉。想不出来可以直接看下面式子。

\[ \begin{aligned} &\sum_{j\geqslant i}f_j\frac{j!}{i!} \cdot \frac{\sum_{j\geqslant k \geqslant i } \binom{j-i}{k-i} (-1)^{k-i}}{(j-i)!} \newline =&\sum_{j\geqslant i}f_j\frac{j!}{i!} \cdot \frac{(1-1)^{j-i}}{(j-i)!} \end{aligned} \]

右下方的分母和左侧分数扔一起是一个非常典型的组合数。

\[ \begin{aligned} &\sum_{j\geqslant i}f_j\frac{j!}{i!} \cdot \frac{(1-1)^{j-i}}{(j-i)!} \newline =&\sum_{j\geqslant i}f_j\binom ji 0^{j-i} \end{aligned} \]

注意，在组合数学中，\(0^0=1\)。
于是很容易地发现，求和号右边的式子值非零，当且仅当 \(i=j\)。

于是就出来了：

\[ \begin{aligned} &\sum_{j\geqslant i}f_j\binom ji 0^{j-i}\newline =&f_i\binom ii 0^0 \newline =&f_i \end{aligned} \]

证毕。

例题

分特产

题目链接

题意

\(m\) 种特产，\(n\) 个人，每种特产 \(s_i\) 个。

人有标号，两个特产相同当且仅当其种类相同。

求让每个人都拿到至少一份特产的分配方案总数，答案对 \(10^9+7\) 取模。

题解

首先，记住开头给你的式子。

然后把下面的东西看一遍，这应该是二项式反演的基本套路。

大体上设两个东西，\(g_i\) 和 \(f_i\)。这里设 \(g_i\) 为钦定 \(i\) 个人不满足要求（即没有特产），其他人随意分配（可能也没有）的方案数，然后 \(f_i\) 为恰好 \(i\) 个人没有特产，其他人都有特产的方案总数。

然后模仿条件式，用 \(f_i\) 表示 \(g_i\)。

容易发现：

1. 对于 \(g_i\)，每一个 \(f_j,j\in [i,n]\) 都一定被包含在里面。
2. 对于每一个包含在里面的 \(f_j\)，被钦定的集合会不同，一共有 \(\binom ji\) 个，所以每个 \(f_j\) 被算了 \(\binom ji\) 次。

综上，\(g_i = \sum_{j=i}^n \binom ji f_j\)。

二项式反演的常见入手点就是设 \(g,f\)。其中 \(g_i\) 表示钦定集合中 \(i\) 个元素满足/不满足要求，其他不管；\(f_i\) 表示集合中恰好 \(i\) 个元素满足/不满足要求（是否满足与 \(g\) 一致）。在此之后用 \(f_i\) 表示 \(g_i\)，二项式反演之后问题就变化成了求 \(g\)。

然后大力二项式反演，套一下式子就能得出来：

\[ f_i = \sum_{j=i}^n \binom ji g_j (-1)^{j-i} \]

答案就是恰好没有不合法元素的方案总数，于是：

\[ \begin{aligned} ans &= f_0 \newline &= \sum_{j=0}^n \binom j0 g_j (-1)^{j-0} \newline &= \sum_{j=0}^n g_j (-1)^j \end{aligned} \]

问题被转化成了求 \(g\)。

假设目前正在求 \(g_i\)，显然只需要有 \(n-i\) 个人需要考虑。由于剩下 \(i-1\) 是钦定不合法的，我们不用考虑；但是非常魔法的事情来了：由于这 \(n-i\) 个人是随便排列的，我们只需要把特产随意分发就行。

怎么个随意分发法？对于每一种特产 \(x\)，可以转化为：有 \(s_x\) 个无标号小球，装进 \(n-i\) 个有标号盒子里的方案数。直接插板法解决就好啦！显然有 \(s_x-1\) 个空，除此以外，盒子可以为空，所以就是 \(s_x-1\) 加 \(n-i\) 个空，插 \(n-i-1\) 个板的方案数，即 \(\binom{s_x-1+n-i}{n-i-1}\)。

每一种特产的分配方案数互不影响，所以乘起来；同时 \(n\) 个人里面选出来 \(i\) 个钦定不合法，再乘一个 \(\binom ni\)，即：

\[ g_i = \binom ni \prod_{j=1}^m \binom{s_x-1+n-i}{n-i-1} \]

然后代入上面计算答案的式子算就完了。

代码

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
75
76

#include <iostream>

using std::cin;
using std::cout;

namespace tkgs {
    using i32 = int;
    using i64 = long long;
    const i64 mod = 1e9 + 7;

#define N 1005
#define NUM 2005
    namespace mat {
        i64 x, y, tmp;
        void exgcd(const i64& a, const i64& b) {
            if (!b) {
                x = 1, y = 0;
            } else {
                exgcd(b, a % b);
                tmp = x;
                x = y;
                y = tmp - a / b * y;
            }
        }

        i64 inv(const i64& a, const i64& b) {
            exgcd(a, b);
            return x;
        }

        i64 fact[NUM], ifact[NUM];

        void init() {
            const i32 n = 2000;
            fact[0] = ifact[0] = 1;
            for (i32 i = 1; i <= n; ++i)
                fact[i] = fact[i - 1] * i % mod;
            ifact[n] = inv(fact[n], mod);
            for (i32 i = n - 1; i; --i)
                ifact[i] = ifact[i + 1] * (i + 1) % mod;
        }

        i64 getC(i32 a, i32 b) {
            if (a < b)
                return 0;
            else
                return fact[a] * ifact[b] % mod * ifact[a - b] % mod;
        }
    }  // namespace mat 实现了初始化阶乘与阶乘逆元，求组合数

    i32 s[N], n, m;

    i64 g(i64 i) {
        i64 res = 1;
        for (i32 j = 1; j <= m; ++j)
            res = res * mat::getC(s[j] + n - i - 1, n - i - 1) % mod;
        res = res * mat::getC(n, i) % mod;
        return res;
    }

    void main() {
        cin >> n >> m;
        for (i32 i = 1; i <= m; ++i)
            cin >> s[i];
        mat::init();
        i64 ans = 0;
        for (i32 j = 0; j < n; ++j)
            (ans += g(j) * ((j & 1) ? -1 : 1)) %= mod;
        cout << (ans % mod + mod) % mod;
    }
}  // namespace tkgs

int main() {
    tkgs::main();
    return 0;
}

ABC309G