容斥原理学习笔记
Terac
·
·
算法·理论
前言
可能需要一点二项式定理和二项式反演的相关知识。
有许多不足还请指出。
公式
经典容斥
$$\left\vert\bigcup\limits_{i=1}^nA_i\right\vert=\sum\limits_{k=1}^n(-1)^{k-1}\sum\limits_{1\le i_1< i_2<\cdots<i_k\le n}\left\vert A_{i_1}\bigcap A_{i_2}\bigcap\cdots\bigcap A_{i_k}\right\vert$$
可以用数学归纳法严格证明，我有个简单点的。
考虑 $S$ 中任一元素 $x$，若共有 $m$ 个集合包含 $x$，其对答案的贡献为
$$\begin{aligned}\sum\limits_{k=1}^m\dbinom{m}{k}(-1)^{k-1}&=-\sum\limits_{k=1}^m\dbinom{m}{k}(-1)^k\\&=-\sum\limits_{k=0}^m\dbinom{m}{k}(-1)^k+1\\&=-(1-1)^m+1\\&=1\end{aligned}$$
即每个元素都仅对答案产生 $1$ 的贡献。
### 组合容斥
组合容斥中，容斥系数变为了组合数。
有个简单的引例，若 $g(S)=\sum\limits_{S\subseteq T}f(T)$，则有
$$f(S)=\sum\limits_{S\subseteq T}(-1)^{\left\vert T\right\vert-\left\vert S\right\vert}g(T)$$
证明如下：
$$\begin{aligned}\text{LHS}&=\sum\limits_{S\subseteq T}(-1)^{\left\vert T\right\vert-\left\vert S\right\vert}g(T)\\&=\sum\limits_{S\subseteq T}(-1)^{\left\vert T\right\vert-\left\vert S\right\vert}\sum\limits_{T\subseteq Q}f(Q)\\&=\sum\limits_{S\subseteq Q}f(Q)\sum\limits_{S\subseteq T\subseteq Q}(-1)^{\left\vert T\right\vert-\left\vert S\right\vert}\\&=\sum\limits_{S\subseteq Q}f(Q)\sum\limits_{T\subseteq Q\backslash S}(-1)^{\left\vert T\right\vert}\end{aligned}$$
考察式子右半边，令 $F(S)=\sum\limits_{T\subseteq S}(-1)^{\left\vert T\right\vert}$，则
$$F(S)=\sum\limits_{i=0}^{|S|}(-1)^i\dbinom{|S|}{i}=(1-1)^{|S|}=\left[|S|=0\right]$$
即 $\text{LHS}=\sum\limits_{S\subseteq Q}f(Q)[Q\backslash S=0]=f(S)$。
现在改变 $f,g$ 的含义，$f(i),g(i)$ 表示所有 $\left\vert S\right\vert =i$ 的 $f(S),g(S)$ 之和，发现每个大小为 $i$ 的集合任选 $k$ 个都会对 $g(k)$ 产生 $f(i)$ 的贡献，即 $g(k)=\sum\limits_{i=k}^n \dbinom{i}{k}f(i)$，由二项式反演得
$$f(k)=\sum\limits_{i=k}^n(-1)^{i-k}\dbinom{i}{k}g(i)$$
有的题容斥系数可能更为复杂，对于如何求容斥系数，可以对每种情况考虑其应被计算次数，并列出方程来求解。
### $\min-\max$ 容斥
给定集合 $S$，$\max(S)$ 表示 $S$ 中最大值，$\min(S)$ 表示 $S$ 中最小值，则有
$$\max(S)=\sum\limits_{T\subseteq S}(-1)^{\left\vert T\right\vert-1}\min(T)$$
$$\min(S)=\sum\limits_{T\subseteq S}(-1)^{\left\vert T\right\vert-1}\max(T)$$
对第一个式子证明。将 $S$ 中的元素从大到小排序，考虑第 $k+1$ 大的应元素被计算几次。
对于第 $k+1$ 大的元素，当它以 $\min(T)$ 呈现时，说明 $T$ 中的元素均是第 $1$ 至第 $k+1$ 大的，且必须包含第 $k+1$ 大的元素。
故第 $k+1$ 个数会被计算 $\sum\limits_{i=0}^k\dbinom{k}{i}(-1)^{i}=(1-1)^k=0$ 次。
特别地，当 $k=0$ 时，会被计算一次，即只有 $\max(S)$ 被计算了一次。
$\min(S)$ 的证明同理。
$\min-\max$ 容斥还可以推广到第 $k$ 大，$\max_k(S)$ 表示集合 $S$ 中第 $k$ 大的元素，设 $f(i)$ 为容斥系数，则 $\max_k(S)=\sum\limits_{T\subseteq S} f(\left\vert T\right\vert)\min(T)$。
对于第 $x+1$ 大的元素，我们希望它被计算 $\left[x+1=k\right]$ 次，可列出方程
$$[x+1=k]=\sum\limits_{i=0}^x\dbinom{x}{i}f(i+1)$$
由二项式反演得
$$\begin{aligned}f(x+1)&=\sum\limits_{i=0}^x(-1)^{x-i}\dbinom{x}{i}\left[i+1=k\right]\\&=(-1)^{x-(k-1)}\dbinom{x}{k-1}\end{aligned}$$
$$f(x)=(-1)^{x-k}\dbinom{x-1}{k-1}$$
即
$$\operatorname{max}_k(S)=\sum\limits_{T\subseteq S} (-1)^{\left\vert T\right\vert -k}\dbinom{\left\vert T\right\vert-1}{k-1}\min(T)$$
主要用来解决集合概率问题。
## 例题
### BZOJ3589 动态树
给你一棵 $n$ 个点的树，$q$ 次操作，支持
1. $u$ 子树内每个点权加 $k
- 查询 k 条链的并集点权和
保证给出的链深度递增。
1\le n,q\le2\times 10^5,1\le k\le5
直接求并不好求，可以用容斥把问题转化为枚举 2^k 种情况求交，这题的链深度递增，求交是相当简单的。
直接树剖维护是 O(2^kn\log^2 n) 的，去到了 10^9。
因为这题的链深度递增，所以链求和可以直接维护到根的路径上点权和，作差就可以了，这样一次修改是 O(\log n)，一次查询是 O(2^k\log n)，总复杂度是 O(2^kn\log n)，去掉了一个 \log。
然后对于 u 子树内的一点 v，一次加 k 会使 v 处增加 (dep_v-dep_u+1)\times k=dep_v\times k-(dep_u-1)\times k，前后两部分分开维护即可。
CQOI2012 局部极小值
对于一个 n\times m 的矩阵，a_{i,j} 被认为是好的当且仅当 a_{i,j} 比其周围 8 个数均更小。给出矩阵中好的元素位置，求可能的矩阵方案数。
所有的 a_{i,j} 构成一个 \left[1,nm\right] 的排列。
1\le n \le 4,1\le m\le 7
为保证构造矩阵合法，可以从小到大填数，目标位置周围显然不能填。
发现最多可存在的好的元素数量很少，可以把这些位置压缩成一个状态进行 dp，关键点位置的转移直接从前驱转移即可，未填数的关键点周围不可转移，其他位置随便放即可，转移方程很好写。
注意到这样 dp 出来的方案数可能会包含更多的关键点，所以要容斥一下，具体而言，若题目给出 i 个关键点，最多存在 p 个关键点，则答案为 \sum\limits_{k=0}^{p-i}(-1)^kf_{i+k}。
因为 p 很小，所以直接搜索，在原有集合上扩展，每次把多一个的答案减掉即可。
复杂度不太会算，跑得挺快。
P4859 已经没什么好害怕的了
给出序列 a,b，一个排列 p 的权值为 \sum\limits_{i=1}^n\left[a_i>b_{p_i}\right]，求权值为 k 的排列个数。
1\le n \le 2\times 10^3
简化题意的 k 是原题的 \dfrac{n+k}{2}。
考虑 dp，先将 a,b 排序，发现当 a_i 选择一个比它小的 b_{p_i} 时，对后面的选择不会有本质影响，而选择比它大的 b_{p_i} 会很复杂。
这启发我们在 dp 中设计匹配个数的状态，最后统一分配剩下的 b_i，f_{i,j} 表示考虑到第 i 项，有 j 个 k 满足 a_k>b_{p_k} 的情况数，记 q_i 表示 b 序列中比 a_i 小的元素个数个数，有转移方程 f_{i,j}=f_{i-1,j}+(q_i-j+1)f_{i-1,j-1}。
之后考虑剩下 b_i 对答案的影响，令 g_i=(n-i)!f_{n,i}，表示剩下的数任意放的情况数，发现可能会产生更多的匹配，且同一种排列可能会被计算多次，考虑组合容斥。
令 h_i 表示权值恰好等于 i 的排列数，有
g_k=\sum\limits_{i=k}^n\dbinom{i}{k}h_i
可以理解为 h_i 中的每种排列从 i 个匹配中任取 k 个出来都会对 g_k 有 1 的贡献。
由二项式反演得
h_k=\sum\limits_{i=k}^{n}(-1)^{i-k} \dbinom{i}{k}g_i
SCOI2010 幸运数字
一个数字是幸运数字当且仅当它每一位均由 6 或 8 组成。
一个数字是类幸运数字当且仅当它是幸运数字的倍数。
求区间 \left[l,r\right] 内类幸运数字的个数。
1\le l\le r\le 10^{10}
发现最多只有 2046 个幸运数字，记为序列 a，可以预处理出来，令 n 表示幸运数字个数。
问题转化为 \left[l,r\right] 中有多少个数是 a 中任意一个数的倍数。
这就是个经典的容斥问题了，其实就是若干个集合求并。
令 f(i) 表示 \left[l,r\right] 中 i 的倍数个数，则
ans=\sum\limits_{k=1}^n (-1)^{k-1}\sum\limits_{1\le i_1< i_2<\cdots<i_k\le n}f(\operatorname{lcm}(a_{i_1},a_{i_2}\cdots,a_{i_k}))
直接做是 O(2^{n}) 的，考虑一些剪枝。
首先可以把这里面有倍数关系的都去掉，这样只剩 943 个数了。
因为 \text{lcm} 大于 r 时肯定不会有贡献了，可以直接返回，这让复杂度大大降低。
然后可以将 a 从大到小排序，让 \text{lcm} 更快超过 r。
这三个剪枝加完就能通过本题了。
BZOJ2839 集合计数
一个 n 个元素的集合，从它的子集（包括空集）中取出若干个集合，使它们的交集大小为 k，求可能的取法总数。
1\le n\le 10^6,0\le k\le n
用 f_i 表示交集大小至少为 i 的答案，首先钦定 i 个交集的元素，共有 \dbinom{n}{i} 种情况，剩下的 n-i 个数组成的集合，共有 2^{n-i} 个子集，每个子集可以选或不选，但不能都不选，要去掉空集，所以共有 2^{2^{n-i}}-1 种取法，即 f_i=\dbinom{n}{i}(2^{2^{n-i}}-1)。
这样也会有一个集合内相同元素算了多次的问题，考虑组合容斥，令 g_i 表示交集大小恰为 i 的答案，有
f_k=\sum\limits_{i=k}^n \dbinom{i}{k}g_i
可理解为在交集 i 个元素中钦定 k 个作为 f_k 中的交集，每次有 g_i 贡献。
由二项式反演得
g_k=\sum\limits_{i=k}^n(-1)^{i-k} \dbinom{i}{k}f_i
HDU4336 Card Collector
有 n 种卡牌，每一时刻有 p_i 的概率得到其中一种，保证 \sum\limits_{i=1}^n p_i=1，求每种卡牌得到至少 1 张的期望时间。
1\le n\le 20
$$E(\max(S))=\sum\limits_{T\subseteq S} (-1)^{\left\vert T\right\vert-1}E(\min(T))$$
$$E(\min(S))=\dfrac{1}{\sum\limits_{i\in S}p_i}$$
$O(2^n)$ 求解。
------------
### HAOI2015 按位或
有一个数，初始为 $0$，每一时刻会选择一个 $\left[0, 2^n\right)$ 内的数，与该数进行或操作。选择 $i$ 的概率是 $p_i$，保证 $\sum\limits_{i=0}^{2^n-1}p_i=1$。问该数变为 $2^{n}-1$ 的期望时间。
$1\le n\le 20
把数抽象成集合，容易看出是刚才那题的加强版。
令 \max(S) 表示集合 S 中拿到最后一个数被或上所需时间，\min(S) 表示集合 S 中或上第一个数所需时间，有
E(\max(S))=\sum\limits_{T\subseteq S} (-1)^{\left\vert T\right\vert-1}E(\min(T))
E(\min(S))=\dfrac{1}{\sum\limits_{S\cap T\ne \varnothing}p_T}
求交集不为空不好弄，可以反着求交集为空的和，S\cap T\ne \varnothing 时 T 是 S 补集的子集，即做一个子集求和，FWT 即可。
时间复杂度 O(2^n n)。
P4707 重返现世
有 n 种元素，每一时刻有 \dfrac{p_i}{m} 的概率得到其中一种，保证 \sum\limits_{i=1}^n p_i=m，
求得到 k 种元素的期望时间。
1\le n\le 10^3,1\le m\le10^4,k\in\left[n-10,n\right]
一道扩展 \min-\max 容斥神仙题。
记 \min(S) 表示集合 S 中得到第一个元素所需时间，\max_k(S) 表示集合 S 中所需时间第 k 大的元素，得到它的时间。因为题目给的是第 k 小，而这里的是第 k 大，为方便处理，令 k=n-k+1，这样 k 变得很小。
可以写出扩展 \min-\max 容斥的期望形式。
E(\operatorname{max}_k(S))=\sum\limits_{T\subseteq S} (-1)^{\left\vert T\right\vert -k}\dbinom{\left\vert T\right\vert-1}{k-1}E(\min(T))
E(\min(S))=\frac{m}{\sum\limits_{i\in S}p_i}
直接做复杂度爆炸，考虑对 E(\min(T)) 相同的一块处理容斥系数。
记 S_i 表示由 \left[1,i\right] 内的若干个数组成的集合。
做一个 dp，f_{i,j,k} 表示所有 T\subseteq S_i 且 \sum\limits_{x\in T}p_x=j，参数为 k 时所有 (-1)^{\left\vert T\right\vert -k}\dbinom{\left\vert T\right\vert-1}{k-1} 之和，答案即为 \sum\limits_{i=1}^mf_{n,i,k}\dfrac{m}{i}。
考虑转移，当 i 不纳入 S_i 中时，f_{i,j,k}=f_{i-1,j,k}。
若 i 纳入 S_i，则会贡献
\begin{aligned}\sum\limits_{T\in S_i} (-1)^{\left\vert T\right\vert -k}\dbinom{\left\vert T\right\vert-1}{k-1}&=\sum\limits_{T\in S_i} (-1)^{\left\vert T\right\vert -k}\left(\dbinom{(\left\vert T\right\vert-1)-1}{(k-1)-1}+\dbinom{(\left\vert T\right\vert-1)-1}{k-1}\right)\\&=\sum\limits_{T\in S_i} (-1)^{(\left\vert T\right\vert-1)-(k-1)}\left(\dbinom{(\left\vert T\right\vert-1)-1}{(k-1)-1}+\dbinom{(\left\vert T\right\vert-1)-1}{k-1}\right)\\&=\sum\limits_{T\in S_i} (-1)^{(\left\vert T\right\vert-1) -(k-1)}\dbinom{(\left\vert T\right\vert-1)-1}{(k-1)-1}+\sum\limits_{T\in S_i} (-1)^{(\left\vert T\right\vert-1)-(k-1)}\dbinom{(\left\vert T\right\vert-1)-1}{k-1}\\&=\sum\limits_{T\in S_i} (-1)^{(\left\vert T\right\vert-1)-(k-1)}\dbinom{(\left\vert T\right\vert-1)-1}{(k-1)-1}-\sum\limits_{T\in S_i} (-1)^{(\left\vert T\right\vert-1)-k}\dbinom{(\left\vert T\right\vert-1)-1}{k-1}\\&=\sum\limits_{T\in S_{i-1}} (-1)^{\left\vert T\right\vert-(k-1)}\dbinom{\left\vert T\right\vert-1}{(k-1)-1}-\sum\limits_{T\in S_{i-1}} (-1)^{\left\vert T\right\vert-k}\dbinom{\left\vert T\right\vert-1}{k-1}\\&=f_{i-1,j-p_i,k-1}-f_{i-1,j-p_i,k}\end{aligned}
时间复杂度 O(nmk)，这里的 k 是新定义的。
后记
这是我第一次写这么长的博客，感觉比较典型的题里面都有了。
参考了学长的容斥原理 pdf，5 年前的 pdf 讲的很细致，感谢 dtz 学长。
只讲了一些最基础的内容，不知道能不能算是容斥原理入门。