容斥学习笔记

容斥的两种基本形式：

$$|\bigcup_{i=1}^n A_i|=\sum_{k=1}^n (-1)^{k+1}(\sum_{1\leq i_1<\cdots<i_k\leq n}|A_{i_1}\cap\cdots\cap A_{i_k}|)\\ |\bigcap_{i=1}^n A_i|=\sum_{S\subseteq [n]}(-1)^{|S|}|\bigcap_{i\in S}\overline{A_i}|$$

$min-max$ 容斥：

$$max\{S\}=\sum_{T\in S} (-1)^{|T|+1}min\{T\}$$

Ribbons on Tree

原题链接

Solution

我们设 $f(S)$ 表示 $S$ 中的所有边都没有被覆盖的方案数，

那么显然，我们要求的式子就是：

$$|\bigcap_{i=1}^n \overline{f(A_i)}|=\sum_{S\in [n]} (-1)^{|S|}|\bigcap_{i\in S}f(A_i)|$$

考虑当 $S$ 已知的时候怎么计算 $f(S)$ 。

此时这幅图被分成了 $|S|+1$ 块，答案显然是每一块的答案乘起来。

每一块内随便分配，方案数显然为 $g_n=[2|n]\cdot (n-1)!!$ 。

接下来最直接的想法就是枚举 $S$ ，然后直接计算。

这显然复杂度高达 $O(2^n)$ ，无法接受。

事实上这是可以通过 $dp$ 来求出的。（也许这是个套路？）

我们设 $dp_{i,j}$ 表示在根节点为 $i$ 的子树中，还有 $j$ 个没有匹配的方案数。

转移时，我们直接树形背包背一下就行。

但是有一个需要特别注意的点：

• 当 $j=0$ 时，边 $(i,fa_i)$ 显然不会被覆盖，这时候我们需要乘上一个容斥系数（ $i=1$ 的时候不需要）。即 $f_{i,0}=-\sum_{j=1}^{sz_i}f_{i,j}\cdot g_j$ 。

最后的答案就是 $f_{1,0}$ 。

code

【集训队作业 $2018$ 】小 $Z$ 的礼物

原题链接

Solution

$min-max$ 容斥 $+$ 轮廓线 $DP$ 。

我们要求的是 $\max\{f(A_i)\}$ ，其中 $f(i)$ 表示 $i$ 被选中的期望步数， $A_i$ 表示第 $i$ 个小 $Z$ 喜欢的礼物。

这个显然可以直接套上 $min-max$ 容斥。

所以现在我们需要求的是： $\sum_{T\in S}(-1)^{|T|+1}\min_{i\in T}(f(i))$ 。

我们考虑对于单独的一个 $T$ ，我们如何计算。

我们设所有能选的方案数为 $sum=2\cdot n\cdot m-n-m$ ，其中能覆盖到 $T$ 中的点的有 $k$ 种，那么选到这 $k$ 种的概率为 $\frac{k}{sum}$ ，那么期望步数就为 $\frac{sum}{k}$ 。

考虑如何求出所有的方案数。

因为可以覆盖每个点的方案都与它相邻，我们考虑轮廓线 $dp$ 。

设 $f_{0/1,S,k}$ 表示当前轮廓为 $S$ ，有 $k$ 个可以覆盖的位置的方案数， $0/1$ 表示当前位置，使用滚动数组，优化空间。

因为容斥系数为 $-1$ ，且只和集合大小的奇偶性有关，我们可以直接将容斥系数放入 $dp$ 数组中，不用再单独开一维。

每次直接大力转移即可。

最后对每个 $dp_{now,T,k}$ 乘上 $\frac{sum}{k}$ 即为答案。

code

Everything on It

原题链接

Solution

简化一下题意：

求有多少个子集族，满足：

• 任意一个子集都是 $[n]$ 的子集
• 任意两个子集互不相同
• $1,2,\cdots,n$ 都出现了至少 $2$ 次。

这个至少出现了 $2$ 次显然是需要容斥的。

我们设 $F(x)$ 表示 $[1..x]$ 每一个数都出现了 $0/1$ 次。

那么最后的答案显然就是：

$$\sum_{i=0}^n(-1)^i\binom{n}{i} F(i)$$

考虑怎么算 $F(i)$ 。

首先，对于剩余的 $n-i$ 个，我们可以任意选择，一共有 $2^{n-i}$ 个 $[n]$ 的子集。

然后我们枚举将这 $i$ 个数分入了 $k$ 个集合，但是有的可以不放。

如果没有后面的限制，显然就是一个斯特林数。但是有后面的限制怎么做？

考虑再加入一个集合作为“垃圾堆”，将所有不放的数放入该集合中，但是我们不知道哪个集合是“垃圾堆”，所以我们再往垃圾堆里面放入一个 $0$ ，这样就可以唯一确定一种分组了。

那么问题就变成了将 $i+1$ 个数放入 $k+1$ 个集合的方案数，就可以直接上斯特林数了。

所以 $F(i)=2^{2^{n-i}}\sum_{k=1}^i (2^{n-i})^kS_{i+1}^{k+1}$ ，其中 $S_i^j$ 表示第二类斯特林数的第 $i$ 行，第 $j$ 列，而 $(2^{n-i})^k$ 是把 $k$ 个集合并入剩下的 $n-i$ 个数里面。

最终的答案就是：

$$\sum_{i=0}^n (-1)^i\binom{n}{i}2^{2^{n-i}}\sum_{k=1}^i (2^{n-i})^k\cdot S_{i+1}^{k+1}$$

code

【HAOI2008】硬币购物

原题链接

Solution

直观想法：每次做一遍多重背包，复杂度可达 $O(4\sum_{i=1}^T s_i)$ （单调队列优化）。

这个复杂度显然爆炸，考虑优化。

考虑到每种物品的限制，我们尝试使用容斥。

即每次减去至少一种物品不合法，加上至少两种物品不合法，减去至少三种物品不合法，加上至少四种物品合法的方案数。

考虑这个怎么计算。

如果我们将每个物品看做无限个，那么我们可以用完全背包得到答案。

对于第 $i$ 种物品不合法，我们可以钦定它先选了 $(d_i+1)$ 个，剩下的钱随便选，答案为 $f[s-(d_i+1)\cdot c_i]$ 。

对于多个物品，我们类似的求就行了。

code