前言
可能需要一点二项式定理和二项式反演的相关知识。
有许多不足还请指出。
公式
经典容斥
\(A_1,A_2,\cdots,A_n\) 均为有限集，\(A_i\subseteq S\)，则
\[\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\) 次操作，支持
- \(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\)
题解
\(\min-\max\) 容斥基础运用，令 \(\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_{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 学长。
只讲了一些最基础的内容，不知道能不能算是容斥原理入门。
标签：right,vert,limits,sum,容斥,笔记,dbinom,原理,left From： https://www.cnblogs.com/Terac/p/18034435