容斥与反演概论

1. 基础容斥思想

有一个属性集合 $U$ 和若干元素。

假定任给一个 $S \subset U$ 都可以快速查询至少满足 $S$ 中所有属性的元素的数量 $f (S)$ 。（定义 $f (\emptyset) = 0$ ）

则我们得到，至少有一种属性的物品数量为

\sum_{S \subset U} f (S) (- 1)^{| S | + 1}

证明：考虑一个含有 $n$ 个属性（ $n \geq 1$ ）的物品在枚举 $S$ 的时候的计算次数：

\sum_{k = 1}^{n} (\binom{n}{k}) (- 1)^{k + 1} = 1

等式容易由二项式定理得到。

有的时候问题不会这么容易，含有 $k$ 个属性的物品对答案的贡献可能为与 $k$ 有关的函数 $g (k)$ 。

我们希望能够使用类似的方式解决问题，关键在于设容斥系数 $σ (x)$ ，即期望答案为

\sum_{S \subset U} f (S) σ (| S |)

相似地，我们考虑含有 $n$ 个属性（ $n \geq 1$ ）的物品的计算次数得到

\sum_{k = 1}^{n} (\binom{n}{k}) σ (n) = g (n)

这是二项卷积，启动 EGF 和多项式科技即可快速计算。

另外一个处理这个式子的方式是二项式反演，之后进行讨论。

如果将上面的问题再度一般化，是一些其他结构而非子集上的性质，我们得到的就不是二项卷积的形式，而是某种更一般的形如

\sum_{k = 1}^{n} p (n, k) σ (n) = g (n)

的东西。此时确定容斥系数自然引向下面对于反演的讨论。

2. 反演的基本概念

对于数列 $f, g$ ，如果 $f$ 可以描述为 $g$ 的某种带权前缀和，即

f (n) = \sum_{k = 0}^{n} A_{n, k} g (k)

或者可以描述成矩阵形式

[\begin{matrix} f (0) \\ f (1) \\ ⋮ \\ f (n) \end{matrix}] = [\begin{matrix} A_{0, 0} \\ A_{1, 0} & A_{1, 1} \\ ⋮ & ⋮ & ⋱ \\ A_{n, 0} & A_{n, 1} & \dots & A_{n, n} \end{matrix}] [\begin{matrix} g (0) \\ g (1) \\ ⋮ \\ g (n) \end{matrix}]

我们进行矩阵求逆，反过来用 $f$ 来表示 $g$ ，该过程称为反演。具体地设逆矩阵为 $A^{- 1}$ ，有

g (n) = \sum_{k = 0}^{n} A_{n, k}^{- 1} f (i)

讲道理这种矩阵写法没什么用，暴力求逆和原来暴力递推计算是一样的。对于具体问题，我们需要挖掘性质得到比较好的式子。

注意前缀和导致矩阵是下三角矩阵于是几乎能够求逆。一般来说我们当然可以扩展定义，令 $f$ 是 $g$ 各项的一个线性组合，但是一般不会遇到这种情况。

另外一种常见的情况是后缀和，即

f (n) = \sum_{k = n}^{m} A_{n, k} g (k)

此时是上三角矩阵，性质与前缀和差别不是很大。

以上为一维的反演，我们类似可以得到高维的反演，方便起见以二维为例：

f (n, m) = \sum_{i = 0}^{n} \sum_{j = 0}^{m} A_{n, i} B_{m, j} g (i, j)

我们先固定 $m$ ，单独对 $n$ 反演：

\sum_{j = 0}^{m} B_{m, j} g (n, j) = \sum_{i = 0}^{n} A_{n, i}^{- 1} f (i, m)

再对 $m$ 反演：

g (n, m) = \sum_{j = 0}^{m} B_{m, j}^{- 1} \sum_{i = 0}^{n} A_{n, i}^{- 1} f (i, j)

整理得到

g (n, m) = \sum_{i = 0}^{n} \sum_{j = 0}^{m} A_{n, i}^{- 1} B_{m, j}^{- 1} f (i, j)

简单来说，高维反演得到的系数是每一位反演得到的系数的乘积。

反演操作也可以看成容斥，比如说前缀和的情形我们用各种奇怪的前缀和 $g (n)$ 容斥出来了原来的 $f (n)$ 。不过在下面的各种反演中，“容斥系数”最后会明确给出，我们无需再费力推导。

3. 子集反演

我们先讨论一类比较一般且更贴近容斥的反演。

考虑关系 $f (S) = \sum_{T \subset S} g (T)$ ，现在希望进行反演，用 $f (T)$ 来表示 $g (S)$ 。
手玩一下可以直接发现这很容斥，似乎直接有

f (S) = \sum_{T \subset S} g (T) ⟺ g (S) = \sum_{T \subset S} (- 1)^{| S - T |} f (T)

怎么证呢。直接代入整理可做，但是一个更巧妙的方式是考虑对前面容斥的式子进行改造，得到恒等式

\sum_{T \subset S} μ (T) = [S = \emptyset]

其中 $μ (T) = (- 1)^{| T |}$ 。为了之后的拓展方便我们还是保留 $μ (T)$ 的抽象形式。

于是有

\begin{aligned} g (S) & = \sum_{T \subset S} g (T) [S - T = \emptyset] \\ = \sum_{T \subset S} g (T) \sum_{R \subset S - T} μ (R) \\ = \sum_{R \subset S} μ (R) \sum_{T \subset S - R} g (T) \\ = \sum_{R \subset S} μ (R) f (S - R) \\ = \sum_{T \subset S} μ (S - T) f (T) \end{aligned}

代入 $μ$ 的定义，证完了。

我们考虑进行一点拓展。如果允许 $S, T$ 为多重集，怎么做？注意多重集的子集会有重复的，求和时因为是枚举子集，重复的仅计一次。

注意上面的推导完全不受影响，关键在于 $μ$ 的选取。一个简单的想法是，既然多重集会带来计数上的困难，那我们就不要多重集，如果 $S$ 中存在重复元素，直接令 $μ (S) = 0$ 。于是我们自然将子集反演推广到了多重集上。

上面的 $μ$ 就是莫比乌斯函数。实际上是可以定义到一般的偏序集上去的，比子集关系还抽象一些，但是因为太过于一般了没什么好性质。

上面的求和中 $T$ 是作为 $S$ 的子集进行求和的；实际上若给定全集 $U$ ，我们还可以做 $T$ 作为 $S$ 的超集进行求和，得到

f (S) = \sum_{S \subset T, T \subset U} g (T) ⟺ g (S) = \sum_{S \subset T, T \subset U} μ (T - S) f (T)

证明：取补集进行对应即可。

我们仔细思考一下这些反演式子的意义。

对于子集和的式子，如果说 $g (T)$ 描述了“恰好”，那么 $f (S)$ 就是某种意义上的“至多”。我们将不容易计数的“恰好”转化成了“至多”，最后反演计算。

超集和的式子中， $f (S)$ 描述了“至少”；或者更形象地说，是“钦定”。我们“钦定”了一部分满足性质，而对其他的位置没有要求，从而简化问题。

4. 莫比乌斯反演

基于上面的讨论平凡。在多重子集反演中令多重集为数分解出来的素因子，就得到莫比乌斯反演。

数论中莫比乌斯函数 $μ (x)$ 的定义可以说与上面多重子集反演中的定义一模一样。

式子：

f (d) = \sum_{x | d} g (x) ⟺ g (d) = \sum_{x | d} μ (\frac{d}{x}) f (x)

f (d) = \sum_{d | x} g (x) ⟺ g (d) = \sum_{d | x} μ (\frac{x}{d}) f (x)

第二个式子省略了上界。

那个容斥的式子也有对应的形式：

\sum_{d | n} μ (d) = [n = 1]

这个式子甚至更常用一些。

莫比乌斯反演在应用中涉及到一些数学推导，这会在其他的文章中进行说明。

5. 二项式反演

在不考虑多重集的子集反演中，如果 $f (S), g (S)$ 的取值仅与 $| S |$ 有关，得到二项式反演：

f (n) = \sum_{k = 0}^{n} (\binom{n}{k}) g (k) ⟺ g (n) = \sum_{k = 0}^{n} (- 1)^{n - k} (\binom{n}{k}) f (k)

f (n) = \sum_{k = n}^{m} (\binom{k}{n}) g (k) ⟺ g (n) = \sum_{k = n}^{m} (- 1)^{k - n} (\binom{k}{n}) f (k)

在一些参考材料中还有多了系数 $(- 1)^{k}$ 的两种形式，这部分可以合到 $g (k)$ 里面，于是没有本质区别。另外这种交错的形式组合意义不够明确，因此我们不予讨论。

同样地容斥也有对应的式子：

\sum_{k = 0}^{n} (- 1)^{k} (\binom{n}{k}) = [n = 0]

上面第一个式子在 EGF 意义下显然。不过并非所有的反演都有这种比较好的对应。

二项式反演比较重要，值得一道经典例题：求 $n$ 个数的错排个数。

不启动二项式反演，直接容斥可做：

我们不要考虑错排，而是考虑钦定 $k$ 个位置不动，这里有一个 $(\binom{n}{k})$ 。不要管其他的元素，随便排得到 $(n - k)!$ 。然后我们发现所有“非错排”与现在得到的答案的关系与前面容斥中举的第一个例子一模一样，于是顺利得到答案为

f (n) = \sum_{k = 0}^{n} (- 1)^{k} (\binom{n}{k}) (n - k)! = n! \sum_{k = 0}^{n} \frac{(- 1)^{k}}{k!}

二项式反演的做法是这样：

我们发现所有的排列可以通过枚举有多少个位置错了得到。设 $f (k)$ 为 $k$ 个数错排的方案数，得到

n! = \sum_{k = 0}^{n} (\binom{n}{k}) f (k)

反演得到与上面相同的式子。可以看到我们无需再想相对复杂的容斥，或者说我们将容斥这一步公式化了。

6. min-max 容斥

不算反演。但它的推导很好体现了二项式反演在推导容斥系数上的应用。

众所周知 $min (x, y) = x + y - max (x, y)$ ，我们可以让 $min, max$ 相互表示，甚至表示出 $kthmax$ 这种东西。

我们考虑对于多元的情况如何拓展。不妨设元素互不相同，否则我们可以对值相同的元素再指定一种顺序，这是不影响推导的。

先写出容斥式子

kthmax (S) = \sum_{T \subset S} min (T) σ (| T |)

考虑 $S$ 中第 $p$ 大的元素的计算次数，我们期望

\sum_{i = 0}^{p - 1} (\binom{p - 1}{i}) σ (i + 1) = [p = k]

将最后的判断部分写成 $[p - 1 = k - 1]$ 进行二项式反演得到

σ (n + 1) = \sum_{i = 0}^{n} (- 1)^{n - i} (\binom{n}{i}) [i = k - 1] = (- 1)^{n + 1 - k} (\binom{n}{k - 1})

代入 $n = | T | - 1$ 得到 $σ (| T |)$ ，代入原式最终得到

kthmax (S) = \sum_{T \subset S} (- 1)^{| T | - k} (\binom{| T | - 1}{k - 1}) min (T)

交换 $min, max$ 显然也成立。

问题来了这有什么用。

在一些问题中， $max$ 和 $min$ 的性质可能有差别。比如 $gcd$ 是取 $min$ ， $lcm$ 是取 $max$ ，二者中显然 $gcd$ 的性质要好得多，可以上莫比乌斯反演。

另外，在关于期望的问题中，求 $max$ 与求 $min$ 难度并不是相同的。对等号两边取期望得到

E (kthmax (S)) = \sum_{T \subset S} (- 1)^{| T | - k} (\binom{| T | - 1}{k - 1}) E (min (T))

这是在做题当中更为常见的应用。

为了更具体地体会到这种转化的好处，做一道例题：

luogu P3175 [HAOI2015] 按位或

设第 $i$ 位经过 $a_{i}$ 次操作变为 $1$ ，则题目即要求 $E (max (a_{1}, \dots, a_{n})) = E (max U)$ 。

这个 $max$ 非常难处理，但是启动 min-max 容斥得到：

E (max U) = \sum_{T \subset U} (- 1)^{| T | - 1} E (min T)

我们发现 $E (min (T))$ 非常好求，这就是一个类似几何分布的形式，容易得到

E (min (T)) = \frac{1}{1 - \sum_{S \subset U - T} P (S)}

进行子集求和（高维前缀和）即可，时间复杂度 $O (n 2^{n})$ 。

7. FFT

FFT 也是反演！

按照之前的套路我们需要一个“容斥”的式子。熟知单位根有性质：

\frac{1}{n} \sum_{k = 0}^{n - 1} ω_{n}^{k x} = [n | x]

现在已知

f (k) = \sum_{j = 0}^{n - 1} g (j) ω_{n}^{j k}

希望用 $g$ 表达 $f$ 。推导几乎是例行公事：

\begin{aligned} g (k) & = \sum_{j = 0}^{n - 1} g (j) [n | (j - k)] \\ = \sum_{j = 0}^{n - 1} g (j) \frac{1}{n} \sum_{p = 0}^{n - 1} ω_{n}^{p (j - k)} \\ = \frac{1}{n} \sum_{p = 0}^{n - 1} ω_{n}^{- p k} \sum_{j = 0}^{n - 1} g (j) ω_{n}^{j p} \\ = \frac{1}{n} \sum_{p = 0}^{n - 1} f (p) ω_{n}^{- p k} \end{aligned}

换一下下标就得到

f (k) = \sum_{j = 0}^{n - 1} g (j) ω_{n}^{j k} ⟺ g (k) = \frac{1}{n} \sum_{j = 0}^{n - 1} f (j) ω_{n}^{- j k}

注意 FFT 与上面几种反演的不同：此处系数 $ω_{n}^{j k}$ 对应的矩阵并不是下三角矩阵。

8. 反演用于卷积的加速计算

1. or 卷积与 and 卷积；子集卷积

我们考虑如何计算 or 卷积：

c_{k} = \sum_{i, j} [i \cup j = k] a_{i} b_{j}

二进制操作和集合运算等效，统一写成集合运算了。

这里的关键是， $[i \cup j = k]$ 的条件难以处理，但是如果变成 $[(i \cup j) \subset k]$ ，就可以拆开：

\begin{aligned} c_{k}^{'} & = \sum_{i, j} [(i \cup j) \subset k] a_{i} b_{j} \\ = \sum_{i, j} [i \subset k] [j \subset k] a_{i} b_{j} \\ = a_{k}^{'} b_{k}^{'} \end{aligned}

其中 $a_{k}^{'}$ 是 $a_{k}$ 的高维前缀和这样。

所以做完了！先给 $a, b$ 都做一下高维前缀和，点乘得到 $c$ ，最后差分回去就得到 $c$ 。

时间复杂度 $O (n 2^{n}) = O (m \log m)$ ， $n$ 是位数， $m = 2^{n}$ 。

and 卷积同理，只不过将前缀和换成了后缀和。

等等所以反演在哪里？

实际上高维差分那一步就是子集反演。我们简单描述为“差分”，但是实际上正确性还是要靠子集反演说明。

以上的操作称为快速莫比乌斯变换（FMT），因为本质上基于子集反演，子集反演基于莫比乌斯函数。

另外一种做这个题的思路是直接构造变换的矩阵和逆矩阵，用类似于 FFT 的方式分治/倍增进行计算，同时也可以推广到 xor 卷积上。这种操作被称为快速沃尔什变换（FWT），在 or 和 and 卷积上与 FMT 等价。这里不予讨论。

实际上实现的时候 FMT 的常数大一些，所以一般都用 FWT 的写法。

or 卷积的一个经典应用是求子集卷积：

c_{k} = \sum_{i, j} [i \cup j = k] [i \cap j = \emptyset] a_{i} b_{j}

$[i \cap j = \emptyset] = [| i | + | j | = | i \cup j |]$ ，于是多开一维记录元素个数：

\begin{aligned} a_{k, n} & = [| k | = n] a_{k} \\ a_{k, n}^{'} & = \sum_{j \subset k} a_{j, n} \\ b_{k, n} & = [| k | = n] b_{k} \\ b_{k, n}^{'} & = \sum_{j \subset k} b_{j, n} \\ c_{k, n} & = \sum_{i, j} [i \cup j = k] [| i | + | j | = n] a_{i} b_{j} \\ c_{k, n}^{'} & = \sum_{j \subset k} c_{j, n} = \sum_{i + j = n} a_{k, i}^{'} b_{k, j}^{'} \end{aligned}

$O (n)$ 次 FMT 和暴力加法卷积都是 $O (n^{2} 2^{n})$ 的，于是总时间复杂度 $O (n^{2} 2^{n}) = O (m \log^{2} m)$ 。

2. gcd 卷积与 lcm 卷积

原理和上面基本一样。将形如 $[gcd (i, j) = k]$ 的形式弱化为 $[k | gcd (i, j)] = [k | i] [k | j]$ 即可拆开计算。

这里的变换变为了 Dirichlet 后缀和 $a_{k}^{'} = \sum_{n | d} a_{d}$ ，逆变换同样是做差分，时间复杂度同埃氏筛是 $O (n \log \log n)$ 的。

另外一种处理思路是使用容斥式子

\sum_{d | n} μ (d) = [n = 1]

容易得到

\begin{aligned} c_{k} & = \sum_{i, j} [gcd (i, j) = k] a_{i} b_{j} \\ = \sum_{i, j} a_{i} b_{j} \sum_{k d | i} \sum_{k d | j} μ (d) \\ = \sum_{k | T} μ (\frac{T}{k}) \sum_{T | i} a_{i} \sum_{T_{j}} b_{j} \end{aligned}

中间枚举了 $T = k d$ 。同样得到对 $a, b$ 分别后缀和，点乘再差分回去的做法。

3. 2 的幂次长度的循环卷积

FFT 本质上是计算了 $n = 2^{m}$ 时的循环卷积。

\begin{aligned} c_{k} & = \sum_{0 \leq i, j < n} [(i + j) mod n = k] a_{i} b_{j} \\ = \sum_{0 \leq i, j < n} [n | (i + j - k)] a_{i} b_{j} \\ = \sum_{0 \leq i, j < n} \frac{1}{n} \sum_{p = 0}^{n - 1} ω_{n}^{p (i + j - k)} a_{i} b_{j} \\ = \frac{1}{n} \sum_{p = 0}^{n - 1} ω_{n}^{- p k} \sum_{i = 0}^{n - 1} ω_{n}^{i k} a_{i} \sum_{j = 0}^{n - 1} ω_{n}^{j k} b_{j} \end{aligned}

于是计算 $c_{k}$ 的方法就是对 $a_{n}, b_{n}$ 做 DFT，点乘再做 IDFT。

循环卷积也可以理解为 $mod x^{n}$ 意义下的多项式乘法。在进行正常的多项式乘法时我们事先将次数扩大了，因此不会“循环”。

一般长度的循环卷积需要 CZT/Bluestein 算法，不属于这里讨论的内容。