容斥原理学习笔记

C_liar · 2023-03-21 18:53:20 · 算法·理论

基本的定义和证明稍微提一下。

摘自 OI-wiki。

设全集 U 中的...展开

容斥模型（口胡）：

全集 U，大小为研究问题的所有可能的情况数（在忽略掉所有元素的属性后）。
元素。
属性，是集合中元素拥有的，可以用来作为划分集合的依据。

例题：

不定方程有限制非负整数解计数

给定不定方程 \sum\limits_{i=1}^nx_i=m 和 n 个限制条件形如 \forall i,x_i\leq b_i，m,b_i\in\mathbb{N}，求非负整数解个数。

若没有限制，插板法易得：

Ans=\binom{n-1}{n+m-1}

若有限制，考虑补集转化。

原式相当于求 \left|\bigcap\limits_{i=1}^{n}S_i\right|，转化为 |U|-\left|\bigcup\limits_{i=1}^{n}\bar {S_i}\right|。

对减数做容斥。

那么相当于对于一些 \bar S_i 的交集计数，即同时满足 x_{a_i}\geq b_{a_i}+1 的解的计数。

考虑对于每个容斥出来的集合，把存在解下限的集合减掉，变成：

\sum_{i=1}^{n}x_i=m-\sum_{i=1}^{k}(b_{a_i}+1)

枚举子集，组合数即可，注意考虑无解。

习题，硬币购物，DP 维护。

完全图子图染色问题

对于 n 阶完全图 G=(V,E)，设 F(S),S\subseteq E 为对图 G'=(V,S) 使用 m 种颜色染色，要求相邻节点必须同色的方案数，求：

Ans=\sum_{S\subseteq E}(-1)^{|S|-1}F(S)

认为 G' 为元素，点 i 和点 j 染同色（表示为 x_i=x_j）为属性，全集为所有 G 的子图。

那么，令属性 x_{i}=x_j 对应的元素的集合为 Q_{i,j}，那么有：

F(S)=\left|\bigcap_{(i,j)\in S}Q_{i,j}\right|

即求交集的大小。

而考虑 Ans，有：

\begin{aligned} Ans&=\sum_{S\subseteq E}(-1)^{|S|-1}F(S)\\ &=\sum_{S\subseteq E}(-1)^{|S|-1}\left|\bigcap_{(i,j)\in S}Q_{i,j}\right|\\ &=\left|\bigcup_{(i,j)\in E}Q_{i,j}\right| \end{aligned}

问题转化为求右边并集的集合大小。

可以补集转化，全集 |U|=m^n，而补集就是所有点异色的方案数，也就是 A_m^n=\frac{m!}{(m-n)!} [1]。

所以，Ans=m^n-\frac{m!}{(m-n)!}。

容斥定理一般化

或者...可以称为反演？

对于两个集合的函数 f(S),g(s)，若：

f(S)=\sum_{T\subseteq S}g(T)

那么有：

g(S)=\sum_{T\subseteq S}(-1)^{|S|-|T|}f(T)

形式类似莫反，(-1)^{k} 即为容斥系数，对应到莫反上就是 \mu(k)，只是集合间的交并补关系不同。

推论（补集形式），就是将集合的子集关系反过来也成立。

有标号 DAG 计数

对 n\leq 5\times 10^3 个点有标号 DAG 计数，答案对 998244353 取模。

将数据范围和模数稍微修改了一下，不然 OI-wiki 上的模数比较毒瘤，不好做（指 NTT）。

upd：我错了...

朴素 DP

考虑 DP，将 DAG 的关键点定为入度为 0 的节点（因为比较好转移，新 DAG 直接接上即可）。

定义 f_{i,j} 为 i 个点的 DAG，有 j 个入度为 0 的点的图的个数。

首先选出 j 个入度为 0 的点，方案数 \binom{i}{j}，接下来的分析将认为 j 个点相同，并且由于已经事先对剩余 i-j 个点带标号分析过，故同样认为剩余 i-j 个点皆相同（方案与顺序无关）。

假设去掉 j 个点后，有 k 个点入度为 0，那么在去掉前 j 个点中的几个必定与所有的 k 个点有连边，即 (2^j-1)^k（因为不能为空集）；j 个点还可以与剩余几个点之间任意连边，方案数为 2^{(i-j-k)j} [2]（即对 j 个点，都有 i-j-k 个点可能与其连接，直接枚举点之间的边是否存在）。

故方程：

f_{i,j}=\binom{i}{j}\sum_{k=1}^{i-j}(2^j-1)^k2^{(i-j-k)j}f_{i-j,k}

边界：f_{1,1}=1，复杂度 O(n^3)，考虑优化。

容斥优化

状态定义为至少 j 个点入度为 0。

直接定义 f_{i} 表示 i 个点的 DAG 个数，可以直接容斥，重复的计数直接利用容斥系数抵消。

考虑选出 j 个点，可以与剩下的 i-j 个点任意连边（因为入度为 0 的点的个数在任意连边后一定不小于 j），有 2^{(i-j)j} 种情况（同上解释）。

故有方程：

f_{i}=\sum_{j=1}^i(-1)^{j-1}\binom{i}{j}2^{(i-j)j}f_{i-j}

时间复杂度 O(n^2)。

多项式优化

先咕，弱联通再咕。

Min-max 容斥

设 x 是第 k 大值，进行映射 f:x\mapsto\{1,2,3,\dots,k\}。

发现 f(\min(x,y))=f(x)\cap f(y)，f(\max(x,y))=f(x)\cup f(y)。

带入容斥式子即可。

[1],[2]:更正了一些 OI-wiki 上的笔误，最早的笔误曾在 2021 年 1 月提出，并且截至现在（2023 年 3 月 21 日）都没有进行修正，希望 OI-wiki 的维护者可以给予足够的重视，否则可能误导相当一部分到 OI-wiki 上自学算法的同学（比如蒟蒻自己 QwQ）。

话说机房里有谁 GitHub 能登上啊...

容斥原理 学习笔记