我会容斥

· · 算法·理论

使用艾弗森括号表示 bool 变量当然也可能会忘。尝试用更好的形式剖析一些经典容斥的原理。

我数学不好，所以会有大量跳步，上下标大量漏，可能会有错误，恳请指出。

1 简单容斥

1.1 逻辑运算

\mathrm{sign}([x])=(-1)^{[x]+1}\\ \neg[x]=(1-[x])\\ [x]\land [y]=[x][y]\\ [x]\lor [y]=\neg(\neg[x]\land \neg[y])\\ =(1-(1-[x])(1-[y]))=[x]+[y]-[x][y]\\ [x]\oplus[y]=[x]+[y]-2[x][y]

1.2 “不存在 a_i”

[\sum_{i=1}^n [a_i]=0]=\bigwedge_{i=1}^n\neg[a_i]=\prod_{i=1}^n(1-[a_i])

其中，最后一个式子等价于：

\sum_{S\subseteq\{1,2,...,n\}} (-1)^{|S|}\prod_{i\in S}[a_i]

1.3 FWT

F_i=\sum_{j\oplus k=i} G_jH_k\\ F_i=\sum_{j=0}^{2^V-1}\sum_{k=0}^{2^V-1}[j\oplus k=i]G_jH_k\\ F_i=\sum_{j=0}^{2^V-1}\sum_{k=0}^{2^V-1}(\prod_{x=0}^{V-1}(1-[i_x\oplus j_x\oplus k_x]))G_jH_k

此时这个形态并不好拆分，考虑并非神之一手：

F_i=\sum_{j=0}^{2^V-1}\sum_{k=0}^{2^V-1}(\prod_{x=0}^{V-1}(\dfrac{1}{2}+(-\dfrac{1}{2})^{[i_x\oplus j_x\oplus k_x]}))G_jH_k\\ F_i=\dfrac{1}{2^V}\sum_{j=0}^{2^V-1}\sum_{k=0}^{2^V-1}(\prod_{x=0}^{V-1}(1+(-1)^{[i_x\oplus j_x\oplus k_x]}))G_jH_k\\ F_i=\dfrac{1}{2^V}\sum_{j=0}^{2^V-1}\sum_{k=0}^{2^V-1}(\prod_{x=0}^{V-1}(1+(-1)^{i_x}(-1)^{j_x}(-1)^{k_x}))G_jH_k\\

接下来考虑分离变量：引进变量 l 表示选择了乘积式的第二项。

F_i=\dfrac{1}{2^V}\sum_{j=0}^{2^V-1}\sum_{k=0}^{2^V-1}\sum_{l=0}^{2^V-1}(-1)^{l\cap j}(-1)^{l\cap k}(-1)^{l\cap i}G_jH_k\\\ F_i=\dfrac{1}{2^V}\sum_{l=0}^{2^V-1}(-1)^{l\cap i}\sum_{j=0}^{2^V-1}(-1)^{l\cap j}\sum_{k=0}^{2^V-1}(-1)^{l\cap k}G_jH_k\\ F_i=\dfrac{1}{2^V}\sum_{l=0}^{2^V-1}(-1)^{l\cap i}(\sum_{j=0}^{2^V-1}(-1)^{l\cap j}G_j)(\sum_{k=0}^{2^V-1}(-1)^{l\cap k}H_k)

定义 \hat F 是 F 的 FWT 后结果。有如下定义式：

\hat{F}_i=\sum_{j=0}^{2^V-1} (-1)^{|i\cap j|} F_j

则有 \hat{F}_i=\hat{G}_i\hat{H}_i。

其实刚才的推导并没有深入 FWT 的本质，但是其充分体现了容斥的自然性。

如果尝试了 3-FWT，使用单位根 \omega 可以用类似的方法推导。

2 例题第一组

2.1 QOJ8184

设 f(a_1,a_2,a_3,...,a_m) 为 a 中不同数的个数。

找到所有正整数序列 a 满足 a_1+a_2+a_3+...+a_m=n 的 f(a_1,a_2,a_3,...,a_m) 的和。对 998244353 取模。

做法如下： $$ \sum_{a}f(a)\\ =\sum_{a}\sum_{p}[p\in \{a\}]\\ =\sum_{a}\sum_{p}(1-[p\notin \{a\}])\\ =\sum_{a}\sum_{p}(1-\prod_{i=1}^m [p\neq a_i])\\ =\sum_{a}\sum_{p}(1-\prod_{i=1}^m (1-[a_i=p]))\\ =\sum_{p}(\sum_{a}1-\sum_{S\subseteq\{1,2,...,m\}}(-1)^{|S|}\sum_{a}\prod_{i\in S} [a_i=p])\\ =\sum_{p}(\sum_{a}1-\sum_{S\subseteq\{1,2,...,m\}}(-1)^{|S|}\sum_{a}\prod_{i=1}^m [[i\in S]\to [a_i=p]])\\ $$ 最后一个式子的意义是“钦定”。 显然上文全都在大炮打蚊子，但是我觉得挺好玩的。 ## 2.2 [P11817](https://www.luogu.com.cn/problem/P11817) 先刻画一下，一种方式是记序列 $a,b$ 表示每条边是由 $a_i \to b_i$。要求 $a_i\neq b_i$，但是还剩下无重边的条件不好刻画。 换个形态，设计长为 $2n$ 的序列 $a$ 进行 $i\to a_{2i-1},i\to a_{2i}$ 这样的连边方式，这太对了吧。于是把所有条件刻画出来。 + 无重边：$a_{2i-1}\neq a_{2i}$。 + 无自环：$i\neq a_{2i-1}$，$i\neq a_{2i}$。 + $1\sim n$ 每个数出现两次。 使用类似上一题的写法： $$ \sum_{a}\prod_{i=1}^n[a_{2i-1}\neq a_{2i}][i\neq a_{2i-1}][i\neq a_{2i}]\\ $$ 为了方便单独拿出里面： $$ [a_{2i-1}\neq a_{2i}][i\neq a_{2i-1}][i\neq a_{2i}]\\ =(1-[a_{2i-1}=a_{2i}])(1-[i=a_{2i-1}])(1-[i=a_{2i}])\\ =1-[a_{2i-1}=a_{2i}]-[i=a_{2i-1}]-[i=a_{2i}]+2[a_{2i-1}=a_{2i}=i] $$ 想一下这个式子啥意思，额这不是小学奥数韦恩图吗。反正乘法原理就是枚举每个 $i$ 选择这四种贡献的哪一个。接下来的部分和容斥没啥关系先不说。 参考：https://www.luogu.com.cn/article/ez7s5j0w ## 2.3 [ARC096C](https://www.luogu.com.cn/problem/AT_arc096_c) 求由若干个长度为 $n$ 的二进制数（$0\sim 2^n -1$）构成的不可重集合 $a$ 的数量，使得对于每一个二进制位，$a$ 中都至少有两个数在这一位上是 $1$。$1\le n\le 3000$。 如法炮制，定义 $\mathrm{count}(a,i)$ 为 $a$ 中第 $i$ 位出现的次数： $$ \sum_{a}\prod_{i=1}^n[\mathrm{count}(a,i)\ge 2]\\ =\sum_{a}\prod_{i=1}^n(1-[\mathrm{count}(a,i)=0]-[\mathrm{count}(a,i)=1]) $$ 看起来已经可以做了。还是乘法原理。如果选了 $[\mathrm{count}(a,i)=0]$ 就是直接丢掉这一位了，不管它。 假设有 $j$ 个数选了 $[\mathrm{count}(a,i)=1]$，这些 $1$ 可以分散到若干个数上，这是类似斯特林数的形式。但是还可以有至多一个 $0$。 然后，在式子里选了 $1$ 的也就是任选的位置可以让一个数分裂成若干个数：如果这是一个全 $0$ 则有 $2^{2^k}-1$ 种选法否则只是 $2^k$。预处理类似斯特林数的 dp 数组即可快速计算。 # 3 其他容斥的新证法 并非很有用，因为数学归纳秒一切。但是好玩。 ## 3.1 二项式反演 可能有点困难。二项式反演要求恰好 $k$ 个。形式化的讲，其需要刻画 $[\sum a_i=k]$。 尝试使用生成函数刻画： $$ \sum_{a}[\sum a_i=k]\\ =[x^k]\sum_a\prod_{i=1}^n(1+a_i(x-1))\\ =\sum_{S\subseteq\{1,2,...,n\}} [x^k] \sum_a \prod_{i\in S} a_i(x-1)\\ =\sum_{S\subseteq\{1,2,...,n\}} [x^k] \sum_a (x-1)^{|S|}\prod_{i\in S}a_i\\ =\sum_{S\subseteq\{1,2,...,n\}} \binom{|S|}{k}(-1)^{|S|-k}\sum_a \prod_{i\in S}a_i\\ $$ 胜利了！这个的意义在于他不仅是可以取第 $k$ 项的，他还可以用单位根反演取 $k$ 的倍数项之类，具体还有没有什么好的拓展我还需要想想。 ## 3.2 Min-Max 反演 扩展 Min-Max 反演例题：P4707。题意：有 $m$ 个小球，小球有 $n$ 种颜色，每次选出一个小球并记录颜色再放回袋子里。问你达到选出 $k$ 种颜色的目标期望花费的操作次数。$1\le k\le n\le 10^3$，$n-k\le 10$，$1\le m\le 10^4$。 期望花费的操作次数也就是对于每个 $p$，第 $p$ 步仍然没有选出 $k$ 种颜色的概率之和。 对应一个序列 $a$，$a_i$ 表示第 $i$ 种颜色被选出的次数。其满足 $\displaystyle \sum_{i=1}^n a_i =p-1$，这个序列被前 $p-1$ 步操作到的方案数为 $\displaystyle \binom{p-1}{a_1,a_2,...,a_n}$。其要求为 $(\sum[a_i>0])<k$ 和上述“二项式反演”的做法是一样的。 ## 3.3 子集反演 对 $T$ 的信息 $f_T$ 做变形： $$ \sum_{T'}\prod_{i=1}^n[[i\in T']=[i\in T]]f_{T'}\\ \sum_{T'}\prod_{i=1}^n(1-[i\in T]+[i\in T'](2[i\in T]-1))f_{T'}\\ $$ 如果注意力比较集中会注意到上面的式子，但是我注意力不够，试了好久。 $$ \sum_{S} \sum_{T'}\prod_{i\notin S}(1-[i\in T])\prod_{i\in S}[i\in T'](2[i\in T]-1)f_{T'}\\ \sum_{S} \prod_{i\notin S}(1-[i\in T]) \prod_{i\in S} (2[i\in T]-1) \sum_{T'}\prod_{i\in S}[i\in T']f_{T'}\\ $$ 可以看到我们已经推完了，但是前面剩下那一大堆是啥？？？ 首先对于 $i\notin S$ 有 $i\in T =0$ 也就是 $i\notin T$，这意味着 $T$ 是 $S$ 的子集。然后对于其中 $i\notin T$ 且 $i \in S$ 的部分会产生 $-1$ 的贡献。 所以其实就是 $[T\subseteq S](-1)^{|S|-|T|}$。 # 4 第二组例题 ## 4.1 [AGC041F](https://www.luogu.com.cn/problem/AT_agc041_f) 格子的形状是笛卡尔树。把每个行拆分开来。考虑定义第 $i$ 个行是否被选记为 $r_i$，第 $i$ 个列是否被选记为 $c_i$。 则一种方案是否被算入答案的代数柿子为： $$ r_i=[\sum_{(x,y)\in rS_i}a_{x,y}=0]\\ c_i=[\sum_{(x,y)\in cS_i}a_{x,y}=0]\\ \prod_{i}\prod_{j}[(H_i,j)\in rS_i](1-r_ic_j) $$ 大概长成这样吧。显然接着推柿子。 $$ \prod_{j}(1-c_j(1-\prod_{i}[(H_i,j)\in rS_i](1-r_i)))\\ =\prod_{j}(1-c_j+c_j\prod_{i}[(H_i,j)\in rS_i](1-r_i)) $$ 当按照笛卡尔树形态 dp 时，一个列第一次出现时枚举其选择乘积式的哪一项，不难发现若选择多个最后一项，其限制是相同的，可以合并，于是只需要记 $0/1$ 状态。复杂度为树形背包复杂度。 ## 4.2 [P14465](https://www.luogu.com.cn/problem/P14465) 说一下这题的好方法。 $$ \prod c_{\min(|i-p_i|,m)}\\ =\prod [|i-p_i|<m]c_{|i-p_i|}+[|i-p_i|\ge m]c_{m}\\ =\prod [|i-p_i|<m]c_{|i-p_i|}+(1-[|i-p_i|<m])c_{m}\\ =\prod c_m+[|i-p_i|<m](c_{|i-p_i|}-c_m) $$ 这个柿子太爽了。可以钦定一个位置是选择第二项还是第一项。 后面只需要直接状压前后共 $2m-1$ 个位置的选择状态并 dp 即可。不需要其他题解里说的大分讨。 ## 4.3 [AGC070B](https://www.luogu.com.cn/problem/AT_agc070_b) 考虑统计一个图 $i\to q_i$ 的权值和。我们为这个图的奇环赋 $2$ 的权值，为这个图的偶环赋 $0$ 的权值。可以写成： $$ \prod_{c\in \mathrm{CYCLE}(G)} (0+2[c\text{ is odd}])\\ =\prod_{c\in \mathrm{CYCLE}(G)} (1+-1+2[c\text{ is odd}]) $$ 这个式子的意思是选出一些环并给偶环统计 $-1$ 的系数，奇环统计 $1$ 的系数。 考虑枚举被钦定为环上节点的集合 $S$，打表或严谨证明可以发现若 $|S|>1$ 则权值为 $0$。实际上这是一个经典的结论（至少我见过），不过能想起来这个结论也并非容易。 接下来钦定在集合 $S$ 中选出的树边，每选出一条获取 $-1$ 的系数。显然其构成若干条链，由于 $|S|\le 1$ 所以只有一条直链被选。没被选的点只需要不选择父亲即可。所有事情可以 $O(n)$ 计算。 ## 4.4 [QOJ15326](https://qoj.ac/problem/15326) 手玩并注意到一个合法的线段树的合法权值方案为： 若一个点有两个叶子，则这两个叶子的权值不同，满足上述限制的前提下，有 $c$ 种这样的点，则方案为 $2^{c-1}$。 证明不难。 若有若干个权值不同的叶子被合并 $a$，若干个权值相同的叶子被合并 $b$，产生的贡献应该是 $[b=0]2^{a}$。 和 4.3 的结论一样，钦定若干个权值不同的叶子被合并 $a$，若干个权值相同的叶子被合并 $b$，系数为 $1^a(-1)^b$。 由于“三角剖分等于线段树”，我们可以发现：剩下乱选的方案是卡特兰数的形式。于是我们只需要计算因为我们的钦定而把 $n$ 个物体合并成了 $k$ 个物体的方案数即可。 这是经典问题，考虑对原序列分治，设 $f_{i,j,0/1,0/1}$ 表示分治区间 $i$ 中合并成了 $j$ 个物体，左右端点是否已被合并。 转移是卷积形式，可以 NTT，复杂度 2 log。 # 5 其他容斥问题 警告：没有使用上文的方法，部分跑题。但是讲容斥不讲这些可能不好。 ## 5.1 [P11714](https://www.luogu.com.cn/problem/P11714) 该来的总会来的。题意：计数图 $G=(V,E)$，有新图 $G'=(V,E')$，且 $E'\subseteq E$，$G'$ 强连通的方案数。$1\le n\le 15$。 关键性质：对于一个**非强连通图**，其缩点后形成一个大小不为 $1$ 的 DAG。 第一步容斥：每步枚举缩点后的 DAG 上，入度为 $0$ 的点集合 $S$，并删除这些点。注意此处并不是那些原图上的点，而是缩完了剩下的点数。对其赋 $(-1)^{|S|+1}$ 的权值。我们可以用类似子集反演的方法说明，进行若干次操作后，这样可以给每个大小不为 $1$ 的 DAG 删空并赋 $1$ 的权值。 接下来，确定原图上被缩成入度为 $0$ 的点的点集 $S'$，定义 $g_{S'}$ 为集合 $S'$ 被分成若干个强连通图（相当于缩点）并乘上系数的方案数。$g$ 的转移较为简单。 接下来设计 $f_{T}$ 表示 $T$ 集合内的答案。枚举 $S'\subsetneq T$ 即可转移。其中 $S'$ 到 $T$ 可以任意连边，需要预处理两个集合之间的边数。 时间复杂度依实现，可以做到 $O(2^nn+3^n)$。 ## 5.2 [AGC067D](https://www.luogu.com.cn/problem/AT_agc067_d) 首先钦定 $1,2,...,n-1,n$ 是唯一的排列，然后令 $i\to [l_i,r_i](l_i\le i\le r_i)$ 这样连边，其是一个 DAG。这样我们就简洁而优美的刻画了形态。 类似主旋律容斥，钦定一个无入度点集合 $S$，系数为 $(-1)^{|S|+1}$。其他点的区间无法跨过任意一个 $S$ 中的点，所以各部分独立。转移非常简单。 难点在于想到 DAG 的转化，感觉知道可以删掉必匹配点是很容易的，但是能想到是 DAG 有点难啊！虽然其实是一个东西。 ## 5.3 [P10104](https://www.luogu.com.cn/problem/P10104) 考虑 $m=0$：假设 $a_{n+1}=C$，只需要最后和 $a_{n+1}=C-1$ 的方案相减即可得到答案，转化为异或和 $=0$。 数位 dp。枚举所有数与上界的 LCP 的最小值，后面会有一个数开始失控，第一次失控后面的达成条件方案数都可以直接算出，$O(n\log V)$。 考虑 $m>0$：容斥，选择一些边强制钦定相等，容斥系数 $-1$，划分成了若干个连通块，每个连通块内限制为 $a$ 的最小值的限制。 预处理联通块内的容斥系数和，这可以使用集合幂级数 $\ln$ 或者暴力 $O(3^n)$。我们也要暴力算出由连通块内最小值所构成的集合，每一个都做一遍“问题 $m=0$”。 记录 $f_{S,T}$ 表示当前连通块集合为 $S$，最小值集合为 $T$。复杂度 $4^n$。但是有说法是合并联通块的状态只有 $n2^n$ 种。$O(n3^n)$。 具体说法一下。首先先给 $a$ 排序。然后是按照最小值从小往大转移。我们需要记录当前选了哪些数和已经选了哪些最小值。 转移时，非最小值除外，剩下的位置最小值一定选了一个序列上的前缀，可以使用最大的最小值位置记录。则只需要记录非最小值的集合和最大的最小值位置，信息量 $O(n2^n)$。转移暴力合并。 ## 5.4 其他技巧 点边容斥：对于树上的一个点集，其构成的连通块数为 $\displaystyle \sum_{u\in V} [u\in S]-\sum_{(u,v)\in E} [u\in S][v\in S]$。 网格版点边容斥：对于网格上的一个点集，其构成的连通块数为 $\displaystyle \sum_{(x,y)} [(x,y)\in S]-\sum_{(x,y)} [(x,y)\in S][(x,y+1)\in S]-\sum_{(x,y)} [(x,y)\in S][(x+1,y)\in S]+\sum_{(x,y)} [(x,y)\in S][(x,y+1)\in S][(x+1,y)\in S][(x+1,y+1)\in S]$。 由于上面两个式子都写成了和这次讲的内容一样的形式，所以我觉得这也是可以用暴力推式子的方法的。但是并不直观。 # 6 总结 本文和上一篇“我不会容斥”有一些重叠。也补充了很多。 容斥是一门很有趣的学问，本文中的容斥式子大多都是使用 bool 变量推式子的方式。这是帮助做题人梳理容斥系数和容斥方法的好技巧。 其中比较奇怪的可能是 3.3 子集反演中的式子，这个应该可以推广到莫比乌斯反演，但是有点复杂，懒了。有人写了这种推式子的可以发出来并批评我。 希望这个技巧可以让“我”和理解这篇文章的人受益。如果写的不好也请批评。