容斥原理的食用方法

· · 个人记录

容斥难！计数难！但是最后还是要靠自己把它想懂才行...

基本定义

我们先来定义一些东西...

容斥原理是作用在集合的集合上的，习惯上我们把第一个集合叫集合，第二个集合叫限制。一个方案如果满足一个限制那么它就是这个限制的一个元素。那么接下来几乎所有问题都是类似的：你要求怎么怎么样的满足一个集合中的一些限制，求方案数（集合大小）。

子集反演

其实不应该先提到这家伙的...我们来看看它的柿子。

f(S)=\sum_{T\subseteq S} g(T)\Longleftrightarrow g(S)=\sum_{T\subseteq S} (-1)^{|S|-|T|}f(T) $g$ 表示对于所有方案满足的限制恰好是 $S$，此时有多少种可行的方案，换句话说，$g$ 是 $S$ 的交限制的大小减去 $S$ 的补集的并限制。（同样，方案不能在补集中出现） 注意到我的方案实际上是和 $S$ 的补集的并限制的补限制取交了的，用人话说，我考虑的每一个元素都**不可能**满足这个集合以外的元素。 难以理解？举个例子，错排，$f$ 代表 $S$ 中的位置有可能是乱的，但是 $S$ 以外的不可能乱的方案数。$g$ 代表 $S$ 中的位置一定是乱的，$S$ 以外的不可能乱的方案数。 最后考虑一下这些柿子，实际上不理解也没啥问题。 左式表示我枚举每个方案构成的限制集合，称为**钦定**。 它可以反演成右式，表示我先考虑每个限制在 $S$ 中任意选，除去那些只能在 $S$ 的除去一个数子集中任意选，加回来....这个容斥操作。 $$ f(S)=\sum_{S\subseteq T} g(T)\Longleftrightarrow g(S)=\sum_{S\subseteq T} (-1)^{|T|-|S|}f(T) $$ 这个柿子实际上是一个超集，还是说一下吧。 $f$ 表示对于所有方案满足的是 $S$ 的一个超集的方案数。 $g$ 表示对于所有方案满足的是 $S$ 的方案数。 举个例子，还是错排，$f$ 表示我有 $S$ 这些位置一定要乱，并且其它的位置也有可能乱， $g$ 表示我只乱 $S$ 这些位置。 所以左式相当于钦定我乱哪些位置。 --- 可以发现，这个子集卷积更加适用于解决现实情况，即我对于每个方案开一个 bitmask 记录我这个方案满足了哪些限制，现在我想求哪些方案是恰好满足这些限制，又或者求哪些方案是满足这些限制还不止，又或者一定不满足其它限制。这种情况。 --- ### 容斥原理 $$ f(S)=\sum_{T\subseteq S} (-1)^{|T|-1}g(T)\Longleftrightarrow g(S)=\sum_{T\subseteq S} (-1)^{|T|-1}f(T) $$ 把这个柿子写出来，然后就是经典。 $f$ 表示 $S$ 的并限制大小。 $g$ 表示 $S$ 的交限制大小。 这个玩意和上面那个子集容斥最大的不同就是它没有对于方案的限制，那么容斥原理注重的是对集合之间关系的考虑。 转成方案的说法，我们再来给这里的 $f,g$ 下一个精确的定义。 $f$ 表示对于所有方案，至少满足 $S$ 中一种限制的方案数。 $g$ 表示对于所有方案，至少满足 $S$ 中所有限制的方案数。 可以发现，$g$ 是我们见过的。 因此，可以发现我们一共建立了三组转化：**恰好和至少，恰好和至多，至少和至少一个**。 因此容斥实际上就是在捣鼓这三个转化的过程。 我经常见到一个容斥是全集减去不满足某些限制的补集这种操作。冷静下来会发现它求的实际上是满足至少一个的方案数，也就是说容斥原理实际上还有一个形式，而这个形式我们已经耳熟能详了，它便是子集反演的补集表示。 $$ f(S)=\sum_{T\subseteq S} g(T)\Longleftrightarrow g(S)=\sum_{T\subseteq S} (-1)^{|T|}f(S-T) $$ 其中 $g(S)$ 表示恰好 $S$，$f(S)$ 表示至多 $S$。 冷静一下，我们思考一下这其中的含义，重新定义 $f(U-S)$ 表示我只在 $S$ 的补集中随便乱选的方案数。换句话说，我们钦定了 $S$ 里面的每个数一定不选，这个套路是比较常用的，原因是我们比较享受在一个集合里随便乱选的快乐，但是实际上你会发现这其实就是子集卷积的一个超小的变形。 --- ### 二项式反演 二项式反演其实就是上面那三个柿子，如果每个限制本质相同，或者虽然本质不同但是可以放在一起算，那么就可以按照具体限制的数量进行容斥。 ### 莫比乌斯反演 其实是子集反演的一个变形，但是因为它特殊的形式导致理解起来有些不同。 放弃之前所有关于集合、限制、方案的定义，它们在莫比乌斯反演中统统不会用到。 $$ f(n)=\sum_{d|n}g(d)\Longleftrightarrow g(n)=\sum_{d|n}\mu(\frac n d)f(d) $$ $$ f(n)=\sum_{n|d}g(d)\Longleftrightarrow g(n)=\sum_{n|d}\mu(\frac d n)f(d) $$ 这俩就是个柿子，直接套用就可以得到一些神必玩意，比如 $$ n=\sum_{d|n}\varphi(d)\Longleftrightarrow \varphi(n)=\sum_{d|n}\mu(\frac n d)d $$ ### 如何处理容斥问题？ #### 先说莫反。 $$ \sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=k] $$ 这个玩意的求解，考虑构造 $f(k)$ 表示这个矩形当中选出的数的 $\gcd$ 为 $k$ 的倍数的方案数。 $g(k)$ 表示选出 $\gcd$ 恰好为 $k$ 的方案数。 $$ \begin{aligned} f(k)&=\sum_{i=1}^n\sum_{j=1}^m [k|gcd(i,j)]\\ &=\sum_{i=1}^n\sum_{j=1}^m [k|i][k|j]\\ &=\lfloor\frac n k\rfloor\lfloor\frac m k\rfloor\\ &=\sum_{k|d}g(d) \end{aligned} $$ 反演一下 $$ g(k)=\sum_{k|d}\mu(\frac d k)\lfloor\frac n d\rfloor\lfloor\frac m d\rfloor $$ 这就是答案了，但是我们直接枚举 $d$ 显然是 $T$ 的，所以考虑变一下，比如枚举一下 $\frac d k$ 这个数。 $$ g(k)=\sum_{i=1}\mu(i)\lfloor\frac n {di}\rfloor\lfloor\frac m {di}\rfloor $$ 然后整除分块就芜湖了。 --- 当然，实际上的莫反题不用这么做，只需要记住几个结论。 定义 $(f*g)(n)=\sum_{d|n}f(d)g(\frac n d) \begin{aligned} \mu * I &= \epsilon \\ \mu * id&=\varphi\\ \varphi * I&=id \end{aligned}

后面两个柿子实际上是莫反推出来的。

然后还有一个套路，[d|(i,j)]\Leftrightarrow [d|i][d|j]。

这个玩意实际上和容斥没啥关系，剩下的套路大概就要自己去题里摸索了。

一般容斥问题

当这个题里面涉及到 恰好、至少一个 这种对某一个方案的选择有一个强约束的时候，可以用容斥把它拆成一个弱约束，比如至多、至少这样。

对于一个约束暂时无从下手，但是至多（钦定不合法）、至少（钦定合法）这种情况很容易求，此时就应该想到容斥。

容斥还有一个nb地方就是你可以去掉一些麻烦的限制。

例题

ZJOI2016 小星星

朴素dp，f(u,i,S) 表示 u 子树当中选了 S 这个集合并且 i 作为根的方案数，转移需要枚举一个蛾子的集合，枚举蛾子的标号，这样是 3^nn^3 的。

考虑优化，这个地方最烦的在于 S 这个集合不是很能优化，你有一个 |S|=i 这个限制，考虑直接去掉这个限制，那么问题转化为求 f(u,i,S) 表示恰好取到 S 这个集合，g(u,i,S) 表示至多取到 S 这个集合，g 的求法很好办，就是枚举一个 S 然后所有的点都选 S 里面的，然后子集反演一些就是 f，然后就做完了。

这个题的关键是把选的点恰好为 S 这个集合，变成一个选的点至多在 S 当中这样一个容斥。

SHOI2016 黑暗前的幻想乡

看见恰好，考虑至多这么多个建筑公司修路，那么问题变成了我每个边可以染若干种颜色，求生成树个数。显然你直接把不同颜色的染法当成重边，就可以上矩阵树定理硬做了。

bzoj3622 已经没有什么好害怕的了

首先转化一下问题令较大匹配为 k 个，则 k-(n-k)=K,k=\frac {n+K} 2，因此实际上等价于我要选一个恰好 k 个左大于右的点。转化成至少 k 个左大于右，考虑 f(i,j) 表示前 i 小的左侧点中选出 j 对左大于右的匹配一共有多少种选法，那么至少的方案数就是 f(n,i)\times(n-i)!

bzoj2839 集合计数

直接容斥成交集元素个数至少 k 的方案数。

枚举一个交集的大小，考虑剩下元素的选法，剩下了 2^{n-i} 个集合，每个集合可选可不选，但是不能全都不选。

NOIonline #2T3 游戏

容斥一下，就是一个裸的树上背包。