专栏文章

我会容斥

tty_mxzhn
算法·理论参与者 20已保存评论 26

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
26 条
当前快照
1 份
快照标识符
@mlia4mm4
此快照首次捕获于
2026/02/12 01:04
上周
此快照最后确认于
2026/02/19 01:13
10 小时前
查看原文
使用艾弗森括号表示 bool 变量当然也可能会忘。尝试用更好的形式剖析一些经典容斥的原理。
我数学不好，所以会有大量跳步，上下标大量漏，可能会有错误，恳请指出。

1 简单容斥

1.1 逻辑运算

sign([x])=(−1)[x]+1¬[x]=(1−[x])[x]∧[y]=[x][y][x]∨[y]=¬(¬[x]∧¬[y])=(1−(1−[x])(1−[y]))=[x]+[y]−[x][y][x]⊕[y]=[x]+[y]−2[x][y]\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 “不存在 aia_i”

[∑i=1n[ai]=0]=⋀i=1n¬[ai]=∏i=1n(1−[ai])[\sum_{i=1}^n [a_i]=0]=\bigwedge_{i=1}^n\neg[a_i]=\prod_{i=1}^n(1-[a_i])
其中，最后一个式子等价于：
∑S⊆{1,2,...,n}(−1)∣S∣∏i∈S[ai]\sum_{S\subseteq\{1,2,...,n\}} (-1)^{|S|}\prod_{i\in S}[a_i]

1.3 FWT

Fi=∑j⊕k=iGjHkFi=∑j=02V−1∑k=02V−1[j⊕k=i]GjHkFi=∑j=02V−1∑k=02V−1(∏x=0V−1(1−[ix⊕jx⊕kx]))GjHkF_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
此时这个形态并不好拆分，考虑并非神之一手：
Fi=∑j=02V−1∑k=02V−1(∏x=0V−1(12+(−12)[ix⊕jx⊕kx]))GjHkFi=12V∑j=02V−1∑k=02V−1(∏x=0V−1(1+(−1)[ix⊕jx⊕kx]))GjHkFi=12V∑j=02V−1∑k=02V−1(∏x=0V−1(1+(−1)ix(−1)jx(−1)kx))GjHkF_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\\
接下来考虑分离变量：引进变量 ll 表示选择了乘积式的第二项。
Fi=12V∑j=02V−1∑k=02V−1∑l=02V−1(−1)l∩j(−1)l∩k(−1)l∩iGjHk Fi=12V∑l=02V−1(−1)l∩i∑j=02V−1(−1)l∩j∑k=02V−1(−1)l∩kGjHkFi=12V∑l=02V−1(−1)l∩i(∑j=02V−1(−1)l∩jGj)(∑k=02V−1(−1)l∩kHk)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)
定义 F^\hat F 是 FF 的 FWT 后结果。有如下定义式：
F^i=∑j=02V−1(−1)∣i∩j∣Fj\hat{F}_i=\sum_{j=0}^{2^V-1} (-1)^{|i\cap j|} F_j
则有 F^i=G^iH^i\hat{F}_i=\hat{G}_i\hat{H}_i。
其实刚才的推导并没有深入 FWT 的本质，但是其充分体现了容斥的自然性。
如果尝试了 3-FWT，使用单位根 ω\omega 可以用类似的方法推导。

2 例题第一组

2.1 QOJ8184

设 f(a1,a2,a3,...,am)f(a_1,a_2,a_3,...,a_m) 为 aa 中不同数的个数。
找到所有正整数序列 aa 满足 a1+a2+a3+...+am=na_1+a_2+a_3+...+a_m=n 的 f(a1,a2,a3,...,am)f(a_1,a_2,a_3,...,a_m) 的和。对 998244353998244353 取模。
1≤n≤1018,1≤m≤500,m≤n1\le n\le 10^{18},1\le m\le 500,m\le n。
做法如下：
∑af(a)=∑a∑p[p∈{a}]=∑a∑p(1−[p∉{a}])=∑a∑p(1−∏i=1m[p≠ai])=∑a∑p(1−∏i=1m(1−[ai=p]))=∑p(∑a1−∑S⊆{1,2,...,m}(−1)∣S∣∑a∏i∈S[ai=p])=∑p(∑a1−∑S⊆{1,2,...,m}(−1)∣S∣∑a∏i=1m[[i∈S]→[ai=p]])\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

先刻画一下，一种方式是记序列 a,ba,b 表示每条边是由 ai→bia_i \to b_i。要求 ai≠bia_i\neq b_i，但是还剩下无重边的条件不好刻画。
换个形态，设计长为 2n2n 的序列 aa 进行 i→a2i−1,i→a2ii\to a_{2i-1},i\to a_{2i} 这样的连边方式，这太对了吧。于是把所有条件刻画出来。
  • 无重边：a2i−1≠a2ia_{2i-1}\neq a_{2i}。
  • 无自环：i≠a2i−1i\neq a_{2i-1}，i≠a2ii\neq a_{2i}。
  • 1∼n1\sim n 每个数出现两次。
使用类似上一题的写法：
∑a∏i=1n[a2i−1≠a2i][i≠a2i−1][i≠a2i]\sum_{a}\prod_{i=1}^n[a_{2i-1}\neq a_{2i}][i\neq a_{2i-1}][i\neq a_{2i}]\\
为了方便单独拿出里面：
[a2i−1≠a2i][i≠a2i−1][i≠a2i]=(1−[a2i−1=a2i])(1−[i=a2i−1])(1−[i=a2i])=1−[a2i−1=a2i]−[i=a2i−1]−[i=a2i]+2[a2i−1=a2i=i][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]
想一下这个式子啥意思，额这不是小学奥数韦恩图吗。反正乘法原理就是枚举每个 ii 选择这四种贡献的哪一个。接下来的部分和容斥没啥关系先不说。
参考：https://www.luogu.com.cn/article/ez7s5j0w

2.3 ARC096C

求由若干个长度为 nn 的二进制数（0∼2n−10\sim 2^n -1）构成的不可重集合 aa 的数量，使得对于每一个二进制位，aa 中都至少有两个数在这一位上是 11。1≤n≤30001\le n\le 3000。
如法炮制，定义 count(a,i)\mathrm{count}(a,i) 为 aa 中第 ii 位出现的次数：
∑a∏i=1n[count(a,i)≥2]=∑a∏i=1n(1−[count(a,i)=0]−[count(a,i)=1])\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])
看起来已经可以做了。还是乘法原理。如果选了 [count(a,i)=0][\mathrm{count}(a,i)=0] 就是直接丢掉这一位了，不管它。
假设有 jj 个数选了 [count(a,i)=1][\mathrm{count}(a,i)=1]，这些 11 可以分散到若干个数上，这是类似斯特林数的形式。但是还可以有至多一个 00。
然后，在式子里选了 11 的也就是任选的位置可以让一个数分裂成若干个数：如果这是一个全 00 则有 22k−12^{2^k}-1 种选法否则只是 2k2^k。预处理类似斯特林数的 dp 数组即可快速计算。

3 其他容斥的新证法

并非很有用，因为数学归纳秒一切。但是好玩。

3.1 二项式反演

可能有点困难。二项式反演要求恰好 kk 个。形式化的讲，其需要刻画 [∑ai=k][\sum a_i=k]。
尝试使用生成函数刻画：
∑a[∑ai=k]=[xk]∑a∏i=1n(1+ai(x−1))=∑S⊆{1,2,...,n}[xk]∑a∏i∈Sai(x−1)=∑S⊆{1,2,...,n}[xk]∑a(x−1)∣S∣∏i∈Sai=∑S⊆{1,2,...,n}(∣S∣k)(−1)∣S∣−k∑a∏i∈Sai\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\\
胜利了！这个的意义在于他不仅是可以取第 kk 项的，他还可以用单位根反演取 kk 的倍数项之类，具体还有没有什么好的拓展我还需要想想。

3.2 Min-Max 反演

扩展 Min-Max 反演例题：P4707。题意：有 mm 个小球，小球有 nn 种颜色，每次选出一个小球并记录颜色再放回袋子里。问你达到选出 kk 种颜色的目标期望花费的操作次数。1≤k≤n≤1031\le k\le n\le 10^3，n−k≤10n-k\le 10，1≤m≤1041\le m\le 10^4。
期望花费的操作次数也就是对于每个 pp，第 pp 步仍然没有选出 kk 种颜色的概率之和。
对应一个序列 aa，aia_i 表示第 ii 种颜色被选出的次数。其满足 ∑i=1nai=p−1\displaystyle \sum_{i=1}^n a_i =p-1，这个序列被前 p−1p-1 步操作到的方案数为 (p−1a1,a2,...,an)\displaystyle \binom{p-1}{a_1,a_2,...,a_n}。其要求为 (∑[ai>0])<k(\sum[a_i>0])<k 和上述“二项式反演”的做法是一样的。

3.3 子集反演

对 TT 的信息 fTf_T 做变形：
∑T′∏i=1n[[i∈T′]=[i∈T]]fT′∑T′∏i=1n(1−[i∈T]+[i∈T′](2[i∈T]−1))fT′\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'}\\
如果注意力比较集中会注意到上面的式子，但是我注意力不够，试了好久。
∑S∑T′∏i∉S(1−[i∈T])∏i∈S[i∈T′](2[i∈T]−1)fT′∑S∏i∉S(1−[i∈T])∏i∈S(2[i∈T]−1)∑T′∏i∈S[i∈T′]fT′\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∉Si\notin S 有 i∈T=0i\in T =0 也就是 i∉Ti\notin T，这意味着 TT 是 SS 的子集。然后对于其中 i∉Ti\notin T 且 i∈Si \in S 的部分会产生 −1-1 的贡献。
所以其实就是 [T⊆S](−1)∣S∣−∣T∣[T\subseteq S](-1)^{|S|-|T|}。

4 第二组例题

4.1 AGC041F

格子的形状是笛卡尔树。把每个行拆分开来。考虑定义第 ii 个行是否被选记为 rir_i，第 ii 个列是否被选记为 cic_i。
则一种方案是否被算入答案的代数柿子为：
ri=[∑(x,y)∈rSiax,y=0]ci=[∑(x,y)∈cSiax,y=0]∏i∏j[(Hi,j)∈rSi](1−ricj)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)
大概长成这样吧。显然接着推柿子。
∏j(1−cj(1−∏i[(Hi,j)∈rSi](1−ri)))=∏j(1−cj+cj∏i[(Hi,j)∈rSi](1−ri))\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/10/1 状态。复杂度为树形背包复杂度。

4.2 P14465

说一下这题的好方法。
∏cmin⁡(∣i−pi∣,m)=∏[∣i−pi∣<m]c∣i−pi∣+[∣i−pi∣≥m]cm=∏[∣i−pi∣<m]c∣i−pi∣+(1−[∣i−pi∣<m])cm=∏cm+[∣i−pi∣<m](c∣i−pi∣−cm)\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−12m-1 个位置的选择状态并 dp 即可。不需要其他题解里说的大分讨。

4.3 AGC070B

考虑统计一个图 i→qii\to q_i 的权值和。我们为这个图的奇环赋 22 的权值，为这个图的偶环赋 00 的权值。可以写成：
∏c∈CYCLE(G)(0+2[c is odd])=∏c∈CYCLE(G)(1+−1+2[c is odd])\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 的系数，奇环统计 11 的系数。
考虑枚举被钦定为环上节点的集合 SS，打表或严谨证明可以发现若 ∣S∣>1|S|>1 则权值为 00。实际上这是一个经典的结论（至少我见过），不过能想起来这个结论也并非容易。
接下来钦定在集合 SS 中选出的树边，每选出一条获取 −1-1 的系数。显然其构成若干条链，由于 ∣S∣≤1|S|\le 1 所以只有一条直链被选。没被选的点只需要不选择父亲即可。所有事情可以 O(n)O(n) 计算。

4.4 QOJ15326

手玩并注意到一个合法的线段树的合法权值方案为：
若一个点有两个叶子，则这两个叶子的权值不同，满足上述限制的前提下，有 cc 种这样的点，则方案为 2c−12^{c-1}。
证明不难。
若有若干个权值不同的叶子被合并 aa，若干个权值相同的叶子被合并 bb，产生的贡献应该是 [b=0]2a[b=0]2^{a}。
和 4.3 的结论一样，钦定若干个权值不同的叶子被合并 aa，若干个权值相同的叶子被合并 bb，系数为 1a(−1)b1^a(-1)^b。
由于“三角剖分等于线段树”，我们可以发现：剩下乱选的方案是卡特兰数的形式。于是我们只需要计算因为我们的钦定而把 nn 个物体合并成了 kk 个物体的方案数即可。
这是经典问题，考虑对原序列分治，设 fi,j,0/1,0/1f_{i,j,0/1,0/1} 表示分治区间 ii 中合并成了 jj 个物体，左右端点是否已被合并。
转移是卷积形式，可以 NTT，复杂度 2 log。

5 其他容斥问题

警告：没有使用上文的方法，部分跑题。但是讲容斥不讲这些可能不好。

5.1 P11714

该来的总会来的。题意：计数图 G=(V,E)G=(V,E)，有新图 G′=(V,E′)G'=(V,E')，且 E′⊆EE'\subseteq E，G′G' 强连通的方案数。1≤n≤151\le n\le 15。
关键性质：对于一个非强连通图，其缩点后形成一个大小不为 11 的 DAG。
第一步容斥：每步枚举缩点后的 DAG 上，入度为 00 的点集合 SS，并删除这些点。注意此处并不是那些原图上的点，而是缩完了剩下的点数。对其赋 (−1)∣S∣+1(-1)^{|S|+1} 的权值。我们可以用类似子集反演的方法说明，进行若干次操作后，这样可以给每个大小不为 11 的 DAG 删空并赋 11 的权值。
接下来，确定原图上被缩成入度为 00 的点的点集 S′S'，定义 gS′g_{S'} 为集合 S′S' 被分成若干个强连通图（相当于缩点）并乘上系数的方案数。gg 的转移较为简单。
接下来设计 fTf_{T} 表示 TT 集合内的答案。枚举 S′⊊TS'\subsetneq T 即可转移。其中 S′S' 到 TT 可以任意连边，需要预处理两个集合之间的边数。
时间复杂度依实现，可以做到 O(2nn+3n)O(2^nn+3^n)。

5.2 AGC067D

首先钦定 1,2,...,n−1,n1,2,...,n-1,n 是唯一的排列，然后令 i→[li,ri](li≤i≤ri)i\to [l_i,r_i](l_i\le i\le r_i) 这样连边，其是一个 DAG。这样我们就简洁而优美的刻画了形态。
类似主旋律容斥，钦定一个无入度点集合 SS，系数为 (−1)∣S∣+1(-1)^{|S|+1}。其他点的区间无法跨过任意一个 SS 中的点，所以各部分独立。转移非常简单。
难点在于想到 DAG 的转化，感觉知道可以删掉必匹配点是很容易的，但是能想到是 DAG 有点难啊！虽然其实是一个东西。

5.3 P10104

考虑 m=0m=0：假设 an+1=Ca_{n+1}=C，只需要最后和 an+1=C−1a_{n+1}=C-1 的方案相减即可得到答案，转化为异或和 =0=0。
数位 dp。枚举所有数与上界的 LCP 的最小值，后面会有一个数开始失控，第一次失控后面的达成条件方案数都可以直接算出，O(nlog⁡V)O(n\log V)。
考虑 m>0m>0：容斥，选择一些边强制钦定相等，容斥系数 −1-1，划分成了若干个连通块，每个连通块内限制为 aa 的最小值的限制。
预处理联通块内的容斥系数和，这可以使用集合幂级数 ln⁡\ln 或者暴力 O(3n)O(3^n)。我们也要暴力算出由连通块内最小值所构成的集合，每一个都做一遍“问题 m=0m=0”。
记录 fS,Tf_{S,T} 表示当前连通块集合为 SS，最小值集合为 TT。复杂度 4n4^n。但是有说法是合并联通块的状态只有 n2nn2^n 种。O(n3n)O(n3^n)。
具体说法一下。首先先给 aa 排序。然后是按照最小值从小往大转移。我们需要记录当前选了哪些数和已经选了哪些最小值。
转移时，非最小值除外，剩下的位置最小值一定选了一个序列上的前缀，可以使用最大的最小值位置记录。则只需要记录非最小值的集合和最大的最小值位置，信息量 O(n2n)O(n2^n)。转移暴力合并。

5.4 其他技巧

点边容斥：对于树上的一个点集，其构成的连通块数为 ∑u∈V[u∈S]−∑(u,v)∈E[u∈S][v∈S]\displaystyle \sum_{u\in V} [u\in S]-\sum_{(u,v)\in E} [u\in S][v\in S]。
网格版点边容斥：对于网格上的一个点集，其构成的连通块数为 ∑(x,y)[(x,y)∈S]−∑(x,y)[(x,y)∈S][(x,y+1)∈S]−∑(x,y)[(x,y)∈S][(x+1,y)∈S]+∑(x,y)[(x,y)∈S][(x,y+1)∈S][(x+1,y)∈S][(x+1,y+1)∈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 子集反演中的式子，这个应该可以推广到莫比乌斯反演，但是有点复杂，懒了。有人写了这种推式子的可以发出来并批评我。
希望这个技巧可以让“我”和理解这篇文章的人受益。如果写的不好也请批评。

评论

共 26 条评论，欢迎与作者交流。

正在加载评论...