Binomial_Inversion

发表于 2022-02-03 更新于 2022-04-25 分类于笔记

二项式反演

一、反演简介

反演的本质：两个数列的双向求和关系。

最常见的反演，比如前缀和与差分。

定义关系矩阵 $A$ ，则 $f_{n} = \sum_{i = 0}^{\infty} A_{n, i} g_{i}$ 。

即 $F = G \times A$ 。

反过来我们也有 $G = A^{- 1} \times F$ 。

我们有如下结论：

定理：两个互为反演关系的矩阵互逆。

一对互逆矩阵转置后仍然互逆，即：

$A \times B = I \Leftrightarrow A^{T} \times B^{T} = I$

一对互逆矩阵分别数乘 $c (c \neq 0)$ 后仍然互逆，即：

$A \times B = I \Leftrightarrow (c A) \times (c B) = I$

反演中 -1 的幂可以移动：

$\sum_{t = 0}^{\infty} (- 1)^{n - t} A_{n, t} B_{t, m} = [n = m] \Leftrightarrow \sum_{t = 0}^{\infty} (- 1)^{t} A_{n, t} (- 1)^{m} B_{t, m} = [n = m]$

我们想办法证明后面的等式能推出前面的等式。

将后面的等式两边乘上 $(- 1)^{n - m}$ ：

$\sum_{t = 0}^{\infty} (- 1)^{n + t} A_{n, t} B_{t, m} = [n = m] (- 1)^{n - m}$

很显然 $n + t$ 与 $n - t$ 奇偶性相同：

$\sum_{t = 0}^{\infty} (- 1)^{n - t} A_{n, t} B_{t, m} = [n = m] (- 1)^{n - m}$

分类讨论：

如果 $n = m$ ，则等式的右边为 1。
如果 $n \neq m$ ，则等式的右边为 0。

说明 $[n = m] (- 1)^{n - m} = [n = m]$ ，即：

$\sum_{t = 0}^{\infty} (- 1)^{n - t} A_{n, t} B_{t, m} = [n = m]$

即我们从右边的等式推到了左边的等式。

想从左边推到右边的话把这个证明过程倒过来走一遍就行了。

对于多维反演，以二维情况为例，假设两维的关系矩阵分别为 $A, B$ ：

$f_{n, m} = \sum_{i = 0}^{\infty} \sum_{j = 0}^{\infty} A_{n, i} B_{m, j} g_{i, j} \Leftrightarrow g_{n, m} = \sum_{i = 0}^{\infty} \sum_{j = 0}^{\infty} A_{n, i}^{- 1} B_{m, j}^{- 1} g_{i, j}$

二、二项式相关结论

$(\binom{n}{m}) = \frac{n!}{m! (n - m)!} = \frac{n^{\underset{―}{m}}}{m!}$

对称： $(\binom{n}{m}) = (\binom{n}{n - m})$
吸收与释放： $(\binom{n}{m}) = \frac{n}{m} (\binom{n - 1}{m - 1})$
二项式定理：

$(1 + x)^{a} = \sum_{i = 0}^{\infty} (\binom{a}{i}) x^{i}$
递推公式（杨辉三角）：

$(\binom{n}{m}) = (\binom{n - 1}{m - 1}) + (\binom{n - 1}{m})$
平行求和：

$\sum_{i = 0}^{n} (\binom{r + i}{i}) = (\binom{r + n + 1}{n})$

证明：前两项之和为

$(\binom{r}{0}) + (\binom{r + 1}{1}) = (\binom{r + 1}{0}) + (\binom{r + 1}{1}) = (\binom{r + 2}{1})$

然后与 $(\binom{r + 2}{2})$ 求和：

$(\binom{r + 2}{1}) + (\binom{r + 2}{2}) = (\binom{r + 3}{2})$

以此类推，综上得到结论。
上指标求和：

$\sum_{i = 0}^{n} (\binom{i}{m}) = (\binom{n + 1}{m + 1})$

证明： $(\binom{m}{m}) = (\binom{m + 1}{m + 1})$ ，与 $(\binom{m + 1}{m})$ 相加得到 $(\binom{m + 2}{m + 1})$ 。

剩下的递推与上个证明类似，不作赘述。

三、二项式反演

常见形式及其证明：

二项式反演基本形式：

$f_{n} = \sum_{i = 0}^{n} (- 1)^{i} (\binom{n}{i}) g_{i} \Leftrightarrow g_{n} = \sum_{i = 0}^{n} (- 1)^{i} (\binom{n}{i}) f_{i}$

证明该结论即证明 $A_{n, i} = (- 1)^{i} (\binom{n}{i})$ 这个矩阵是自逆的。

证明：

$\begin{aligned} {(A \times A)}_{d, t} = & \sum_{i = 1}^{\infty} A_{d, i} A_{i, t} \\ = & \sum_{i = t}^{d} (- 1)^{i} (\binom{d}{i}) (- 1)^{t} (\binom{i}{t}) \\ = & (- 1)^{t} \sum_{i = t}^{d} (- 1)^{i} \frac{d! i!}{i! (d - i)! t! (i - t)!} \\ = & (- 1)^{t} \sum_{i = t}^{d} (- 1)^{i} \frac{d!}{(d - i)! t! (i - t)!} \\ = & (- 1)^{t} \sum_{i = t}^{d} (- 1)^{i} \frac{d!}{(d - t)! t!} \frac{(d - t)!}{(d - i)! (i - t)!} \\ = & (- 1)^{t} \sum_{i = t}^{d} (- 1)^{i} \frac{d!}{(d - t)! t!} \frac{(d - t)!}{(d - i)! ((d - t) - (d - i))!} \\ = & (- 1)^{t} (\binom{d}{t}) \sum_{i = t}^{d} (- 1)^{i} (\binom{d - t}{d - i}) \\ = & (- 1)^{t} (\binom{d}{t}) (- 1)^{t} \sum_{i = 0}^{d - t} (- 1)^{i + t} (\binom{d - t}{d - t - i}) \\ = & (- 1)^{t} (\binom{d}{t}) (- 1)^{t} \sum_{i = 0}^{d - t} (- 1)^{i} (\binom{d - t}{i}) \\ = & (- 1)^{t} (\binom{d}{t}) (- 1)^{t} (1 - 1)^{d - t} \\ = & [d = t] \end{aligned}$

于是 $A \times A = I$ ，反演成立。

二项式反演的另外一种形式：

$f_{n} = \sum_{i = 0}^{n} (\binom{n}{i}) g_{i} \Leftrightarrow g_{n} = \sum_{i = 0}^{n} (- 1)^{n - i} (\binom{n}{i}) f_{i}$

就是利用我们第一部分讲的那个 -1 的幂可以移动的结论，证明这个形式和我们刚才讲的基本形式是等价的。

如果想证明的话，当然可以先证明这个和上面的基本形式等价，然后再证明基本形式正确，从而证明这个形式正确。

但实际上在这种形式下，我们有更好的证明方法。

证明：

$f_{n} = \sum_{i = 0}^{n} (\binom{n}{i}) g_{i}$

等价于：

$\frac{f_{n}}{n!} = \sum_{i = 0}^{n} \frac{1}{(n - i)!} \frac{g_{i}}{i!}$

这实际上是一个 EGF 的卷积形式：

$\hat{F} = \hat{G} * e^{x} \Leftrightarrow \hat{F} * e^{- x} = \hat{G}$

再换成级数的形式：

$\frac{g_{n}}{n!} = \sum_{i = 0}^{n} \frac{(- 1)^{n - i}}{(n - i)!} \frac{f_{i}}{i!}$

该形式等价于：

$g_{n} = \sum_{i = 0}^{n} (- 1)^{n - i} (\binom{n}{i}) f_{i}$

因为上述证明中我们使用的都是等价，因此所有的推导都可以逆向进行，即两个等式等价。

另一种形式：

$f_{n} = \sum_{i = n}^{\infty} (\binom{i}{n}) g_{i} \Leftrightarrow g_{n} = \sum_{i = n}^{\infty} (- 1)^{i - n} (\binom{i}{n}) f_{i}$

实际上就是将 EGF 证明的那种形式的矩阵进行转置后得到的。

另一种形式：

$f_{n} = \sum_{i = n}^{\infty} (- 1)^{i} (\binom{i}{n}) g_{i} \Leftrightarrow g_{n} = \sum_{i = n}^{\infty} (- 1)^{i} (\binom{i}{n}) f_{i}$

将上面的形式移动 -1 的幂次即可。
错排引入：

求错位排列数 $d_{n}$ 。

我知道你会 $d_{n} = (n - 1) (d_{n - 1} + d_{n - 2})$ 然后矩阵加速，跑得飞快。

但我现在要讲一下这个东西的通项公式是如何使用二项式反演得到的。

每次钦定 $k$ 个位置，它们严格错排，其余位置不动。其中 $k$ 取 $0, 1, 2, \dots, n$ 。

显然这些方案可以不重不漏的覆盖所有排列的方案：

$n! = \sum_{i = 0}^{n} (\binom{n}{i}) d_{i}$

二项式反演：

$\begin{aligned} d_{n} = & \sum_{i = 0}^{n} (- 1)^{n - i} (\binom{n}{i}) i! \\ = & n! \sum_{i = 0}^{n} \frac{(- 1)^{n - i}}{(n - i)!} \\ = & n! \sum_{i = 0}^{n} \frac{(- 1)^{i}}{i!} \end{aligned}$

于是我们得到了 $d_{n}$ 的通项，每项可以 $O (n)$ 计算。

如果想求出前 $n$ 项的具体值的话，根据 $\hat{G} = \hat{F} * e^{- x}$ 卷积，直接 NTT 就是 $O (n \log n)$ 的，和矩阵乘法没差。

但是单次求还是矩阵乘法更胜一筹。

这里拿这个问题不过就是简单应用一下二项式反演。。。
钦定法：

还是错排问题。

我们称 $p_{i} = i$ 的 $i$ 为不动点。

设 $g_{n, k}$ 为恰有 $k$ 个不动点的长度为 $n$ 的排列个数。

设 $f_{n, k}$ 为有 $k$ 个及以上不动点的长度为 $n$ 的排列个数。

那么我们就有：

$f_{n, k} = \sum_{m = k}^{n} (\binom{m}{k}) g_{n, m}$

然后二项式反演：

$g_{n, m} = \sum_{k = m}^{n} (- 1)^{k - m} (\binom{k}{m}) f_{n, k}$

很容易知道：

$f_{n, k} = (\binom{n}{k}) (n - k)! = \frac{n!}{k!}$

代入 $g_{n, m}$ ：

$g_{n, m} = g_{n, m} = \sum_{k = m}^{n} (- 1)^{k - m} (\binom{k}{m}) \frac{n!}{k!}$

我们要求的就是：

$d_{n} = g_{n, 0} = n! \sum_{k = 0}^{n} \frac{(- 1)^{k}}{k!}$

和上面我们求出的通项是一样的。

例题一：P4491 [HAOI2018]染色

差卷积的使用，就是调整序列标号之后再做加法卷积

例题二：P6478 [NOI Online #2 提高组] 游戏

先 DP 后反演

例题三：CF997C Sky Full of Stars

二维二项式反演
反演过后使用二项式定理化简

练习：CF1228E Another Filling the Grid

同样是二维二项式反演
例题的弱化

例题四：P5339 [TJOI2019]唱、跳、rap和篮球

特殊的钦定方法
以及 EGF 计算

练习题 ? 组：

P5400 [CTS2019] 随机立方体
P5401 [CTS2019] 珍珠