二项式反演

定义

直接给出式子：

𝑔𝑖=∑𝑘⩾𝑖(𝑘𝑖)⁢𝑓𝑘→𝑓𝑖=∑𝑘⩾𝑖(𝑘𝑖)⁢(−1)𝑘−𝑖⁢𝑔𝑘

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

证明

前置知识

组合数学常用记号

二项式定理

正文

已知：𝑔𝑖 =∑𝑘⩾𝑖(𝑘𝑖)⁢𝑓𝑘
求证：𝑓𝑖 =∑𝑘⩾𝑖(𝑘𝑖)⁢(−1)𝑘−𝑖⁢𝑔𝑘

把求证右边那个式子单独拿出来，想办法把它导成 𝑓𝑖。

∑𝑘⩾𝑖(𝑘𝑖)⁢(−1)𝑘−𝑖⁢𝑔𝑘=∑𝑘⩾𝑖(𝑘𝑖)⁢(−1)𝑘−𝑖⁢∑𝑗⩾𝑘(𝑗𝑘)⁢𝑓𝑗

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

∑𝑘⩾𝑖(𝑘𝑖)⁢(−1)𝑘−𝑖⁢∑𝑗⩾𝑘(𝑗𝑘)⁢𝑓𝑗=∑𝑗⩾𝑖𝑓𝑗⁡∑𝑗⩾𝑘⩾𝑖(𝑗𝑘)⁢(𝑘𝑖)⁢(−1)𝑘−𝑖=∑𝑗⩾𝑖𝑓𝑗⁡∑𝑗⩾𝑘⩾𝑖𝑗!𝑘!𝑘!(𝑗−𝑘)!𝑖!(𝑘−𝑖)!⁢(−1)𝑘−𝑖=∑𝑗⩾𝑖𝑓𝑗⁡𝑗!𝑖!⁢∑𝑗⩾𝑘⩾𝑖1(𝑗−𝑘)!(𝑘−𝑖)!⁢(−1)𝑘−𝑖

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

上下同乘 (𝑗 −𝑖)!，然后 (𝑗 −𝑘) =[(𝑗 −𝑖) −(𝑘 −𝑖)]，然后就可以轻松化成组合数形式继续往下导公式了。

∑𝑗⩾𝑖𝑓𝑗⁡𝑗!𝑖!⁢∑𝑗⩾𝑘⩾𝑖1(𝑗−𝑘)!(𝑘−𝑖)!⁢(−1)𝑘−𝑖=∑𝑗⩾𝑖𝑓𝑗⁡𝑗!𝑖!⁢∑𝑗⩾𝑘⩾𝑖(𝑗−𝑖)![(𝑗−𝑖)−(𝑘−𝑖)]!(𝑘−𝑖)!(𝑗−𝑖)!⁢(−1)𝑘−𝑖=∑𝑗⩾𝑖𝑓𝑗⁡𝑗!𝑖!⁢∑𝑗⩾𝑘⩾𝑖(𝑗−𝑖𝑘−𝑖)(𝑗−𝑖)!⁢(−1)𝑘−𝑖

换个形式

∑𝑗⩾𝑖𝑓𝑗⁡𝑗!𝑖!⋅∑𝑗⩾𝑘⩾𝑖(𝑗−𝑖𝑘−𝑖)⁢(−1)𝑘−𝑖(𝑗−𝑖)!

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

∑𝑗⩾𝑖𝑓𝑗⁡𝑗!𝑖!⋅∑𝑗⩾𝑘⩾𝑖(𝑗−𝑖𝑘−𝑖)⁢(−1)𝑘−𝑖(𝑗−𝑖)!=∑𝑗⩾𝑖𝑓𝑗⁡𝑗!𝑖!⋅(1−1)𝑗−𝑖(𝑗−𝑖)!

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

∑𝑗⩾𝑖𝑓𝑗⁡𝑗!𝑖!⋅(1−1)𝑗−𝑖(𝑗−𝑖)!=∑𝑗⩾𝑖𝑓𝑗⁡(𝑗𝑖)⁢0𝑗−𝑖

注意，在组合数学中，00 =1。
于是很容易地发现，求和号右边的式子值非零，当且仅当 𝑖 =𝑗。

于是就出来了：

∑𝑗⩾𝑖𝑓𝑗⁡(𝑗𝑖)⁢0𝑗−𝑖=𝑓𝑖⁡(𝑖𝑖)⁢00=𝑓𝑖

证毕。

例题

分特产

题目链接

题意

𝑚 种特产，𝑛 个人，每种特产 𝑠𝑖 个。

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

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

题解

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

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

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

然后模仿条件式，用 𝑓𝑖 表示 𝑔𝑖。

容易发现：

1. 对于 𝑔𝑖，每一个 𝑓𝑗,𝑗 ∈[𝑖,𝑛] 都一定被包含在里面。
2. 对于每一个包含在里面的 𝑓𝑗，被钦定的集合会不同，一共有 (𝑗𝑖) 个，所以每个 𝑓𝑗 被算了 (𝑗𝑖) 次。

综上，𝑔𝑖 =∑𝑛𝑗=𝑖(𝑗𝑖)⁢𝑓𝑗。

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

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

𝑓𝑖=𝑛∑𝑗=𝑖(𝑗𝑖)⁢𝑔𝑗⁡(−1)𝑗−𝑖

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

𝑎⁢𝑛⁢𝑠=𝑓0=𝑛∑𝑗=0(𝑗0)⁢𝑔𝑗⁡(−1)𝑗−0=𝑛∑𝑗=0𝑔𝑗⁡(−1)𝑗

问题被转化成了求 𝑔。

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

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

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

𝑔𝑖=(𝑛𝑖)⁢𝑚∏𝑗=1(𝑠𝑥−1+𝑛−𝑖𝑛−𝑖−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