集合划分容斥学习笔记

在有些时候，当我们无法很好的刻画出一个极大物时（一个极大物可能会被划分成若干非极大物），我们也需要求出一个容斥系数 $H(x)$ ，使得对于所有对极大物的划分方法，每个非极大物的容斥系数的乘积之和，恰好为我们所需要的系数 $F(x)$ 。设 $G(x)$ 为拼接函数，则有 $G(H(x)) = F(x)$ ，比如说 $G(x)$ 在拼接有序的时候一般是 $\frac1{1 - x}$ ，无序的时候一般是 $\exp$ 。

例子：DAG 定向方案数

套路的考虑每次删掉一个独立集来 dp，但是这样会使得本可以一次删掉的独立集被分多次删掉而导致记重。于是我们考虑乘上容斥系数 $h_i$ ，使得 $f_i = \sum_{j = 0}^i \binom ij f_{i - j} h_j$ ，即 $\frac{f_i}{i!} = \sum_{j = 0}^i \frac{f_{i - j}}{(i - j)!} \frac{h_j}{j!}$ 。因为独立集大小无论多少，我们都希望计算 $1$ 的系数，所以 $\forall i, f_i = 1$ 。设 $F(x) = \frac{x^if_i}{i!}, H(x) = \frac{x^ih_i}{i!}$ ，则有 $\frac1{1 - H(x)} = F(x)$ 。

写个求逆就可以发现 $h_i$ 的规律为 $h_i = (-1)^{i - 1}$ ，归纳证明也是简单的。

[AGC058D] Yet Another ABC String

我们考虑将一个字符串划分成若干极长的形如 ABCABCABCABCAB... 的段，比如 BCBABBCCABCAB 会被划分成这样：BC|B|AB|BC|CABCAB。那么我们对于一个合法串的要求就是，每一段的长度都 $\le 2$ 。

但是极长连续段是不太方便刻画的，而如果不考虑极长的限制，一个极长段可能在实际计算方案时被划分成若干子段。所以我们考虑设计一个只和长度有关的容斥系数 $h_i$ ，使得一个极长段的所有划分方案的容斥系数的乘积和为所需的系数 $f_i$ ，则 $f_i = \sum_{j = 0}^i f_{i - j}h_j$ 。

写成生成函数的形式（即 $[x^i]H(x) = h_i, [x^i]F(x) = f_i$ ），也就是 $\frac1{1 - H(x)} = F(x)$ 。

而我们希望极长段的长度 $\le 2$ ，所以长度 $> 2$ 的极长段我们想让其系数为 $0$ ，否则我们希望其系数为 $1$ 。所以在这里， $F(x) = 1 + x + x^2$ ，我们想要倒过来推出 $H(x)$ 。

\frac1{1 - H(x)} = 1 + x + x^2\\ H(x) = x + x^2 - (x + x^2)H(x)\\

然后就可以写出线性递推形式 $h_1 = 1, h_2 = 0, h_i = -h_{i - 1} - h_{i - 2} (i \ge 3)$ 。归纳一下可以得到规律：

h_i = \begin{cases} 1 & i \equiv 1 \pmod 3\\ 0 & i \equiv 2 \pmod 3\\ -1 & i \equiv 0 \pmod 3\\ \end{cases}

当然也可以直接写个求逆然后找规律。于是我们对长度 $\bmod 3 = 1$ 和长度 $\bmod 3 = 0$ 的两种段分别考虑（系数为 $0$ 的不需考虑），得到一个连续段的生成函数：

\begin{aligned} P(a, b, c) &= (a + b + c) \sum_{i \ge 0} a^i b^i c^i - 3 \sum_{i \ge 1} a^i b^i c^i\\ &= \frac{a + b + c - 3abc}{1 - abc}\\ \end{aligned}

答案即为连续段任意拼接起来的生成函数：

[a^Ab^Bc^C]\frac1{1 - P(a, b, c)} = [a^Ab^Bc^C]\frac{1 - abc}{1 + 2abc - a - b - c}

设 $Q(a, b, c) = \frac1{1 + 2abc - a - b - c}$ ，则答案为：

[a^Ab^Bc^C]Q(a, b, c) - [a^{A - 1}b^{B - 1}c^{C - 1}]Q(a, b, c)\\ Q(a, b, c) = \frac1{1 + 2abc - a - b - c}\\ = \frac1{1 - (a + b + c - 2abc)}\\ = \sum_{i \ge 0} (a + b + c - 2abc)^i\\

枚举选择了多少个 $-2abc$ 即可 $O(A + B + C)$ 计算答案。

「2020-2021 集训队作业」Yet Another Permutation Problem

首先最终的排列中间没动的一段一定是一个极长上升连续段，设其长度为 $l$ ，则至少要操作 $n - l$ 次。我们对于一个排列，为了最小化操作次数显然要保留最长的一段。所以一个排列能被 $k$ 次操作得到，至少要有一段长度 $\ge n - k$ 的上升连续段。容斥一下计算无法得到的，就是每个极长上升连续段长度都是 $< n - k$ 的。

这一题中我们也无法较好地刻画出极长上升连续段，所以类似于上一题，我们所需的系数为 $F(x) = \frac{x - x^{n - k}}{1 - x}$ ，类似的推导可以得出规律：

h_i = \begin{cases} 1 & i \equiv 1 \pmod n - k\\ 0 & i \bmod (n - k) \ge 2\\ -1 & i \equiv 0 \pmod n - k\\ \end{cases}

所以这样就可以对于每个 $k$ 做 $O(n^2)$ dp 了：

f_i = \sum_{j = 1}^i \binom ij f_{i - j} h_j

然后可以发现 $h$ 中只有 $O(\frac n{n - k})$ 个位置不为 $0$ ，所以可以调和级数，总复杂度变为 $O(n^2 \ln n)$ 。

[ABC236Ex] Distinct Multiples

我们考虑对元素互不相同这个限制进行容斥，发现这个限制其实就相当于 $\forall 1 \le i < j \le n, a_i \ne a_j$ 。那么我们设 $F(S)$ 表示对于一个集合 $S$ 内的所有 $(x, y)$ 都满足 $a_x = a_y$ ，那么答案就是 $\sum_{S \subseteq E_n} (-1)^{|S|} F(S)$ ，其中 $E_n$ 是直接暴力计算这个东西的时间复杂度为 $O(n2^{|E_n|} \log m)$ ，过不去。

但是显然 $F(S)$ 只和 $S$ 中的边构成的连通块集合有关，所以我们考虑枚举划分集合进行 dp，设 $f_S$ 表示考虑了 $S$ 集合内的答案，则有转移方程：

f_S = \sum_{T \subseteq S} g_{|T|} \left\lfloor \frac m{\operatorname{lcm}(T)} \right\rfloor f_{S - T}

注意，我们为了不计算转移顺序的影响，必须要钦定编号最小的元素在 $T$ 中。

其中 $g_n$ 表示 $n$ 个点所形成的连通边集的容斥系数和。

考虑推导 $g$ 是什么。类似连通图计数，可以得到转移方程：

g_i = h_i - \sum_{j = 1}^{i - 1} \binom{i - 1}{j - 1} g_j h_{i - j}

其中 $h_n$ 表示 $n$ 个点所形成的任意边集的容斥系数和，则 $h_i = \sum_{S \subseteq E_i} (-1)^{|S|}$ 。

发现 $h_1 = 1, h_i = 0 (i \ge 2)$ ，所以转移方程可以写成 $g_1 = 1, g_i = -\binom{i - 1}{i - 2}g_{i - 1} = -(i - 1)g_{i - 1}$ ，得出通项公式 $g_i = (-1)^{i - 1}(i - 1)!$ 。

则 $O(n2^n \log m)$ 预处理出每个子集的 $\operatorname{lcm}$ ， $O(3^n)$ 枚举子集 dp 即可，也可以半在线子集卷积优化到 $O(n^22^n)$ ，但是没必要。

推荐阅读：2023 论文《对互异关系的容斥》by 周子衡。

菜王的 blog