「学习笔记」容斥原理再探

全集 $U$ 种有若干元素，每个元素 $x_i$ 都有若干个不同的属性 $p_j$．令 $A_i$ 为满足第 $i$ 个属性的集合。现有 $n$ 个元素，$m$ 个属性，欲求 $|\bigcap_j^m A_j|$．

艾弗森记号是有力的工具。

$\begin{aligned} |\bigcap_j^m A_j|&=\sum_i^n\prod_j^m[x_i\in A_j] \\ &=\sum_i^n\prod_j^m(1-[x_i\notin A_j]) \\ &=\sum_i^n\sum_{T\subseteq \{1,2,\cdots,m\}}\left((-1)^{|T|}\prod_{j\in T}[x_i\notin A_j]\right) \\ &=\sum_{T\subseteq \{1,2,\cdots,m\}}(-1)^{|T|}\left|\bigcap_{j\in T}\complement _U A_j\right| \end{aligned}$

这就得到了计数问题中容斥原理的常见形式，考虑其组合意义：

计数问题中，全集即为所有方案构成的集合。

$|\bigcap_j^m A_j|$ 意思是，这 $m$ 种限制全部满足的方案数是多少。

$\left|\bigcap_{j\in T}\complement _U A_j\right|$ 的意思是，枚举了一个集合 $T$，强行钦定这些限制是不满足的，一共有多少方案。将其乘上其容斥系数 $(-1)^{|T|}$ 再求和即为所求方案数。

而在一类通过容斥和 dp 解决的问题中，会选择直接带着容斥系数 dp 方案数。且看例题：

「CSP-S 2019」Emiya 家今天的饭

~~就这也叫容斥？~~

第三个限制很愤怒，先不管它，算出所有的方案，再容斥掉不合法的，然后就会发现，只需要一层容斥就可以了。

具体地，枚举哪个主要食材是超了的，在这上面做个 dp，以 $f_{i,j,k}$ 表示考虑了前 $i$ 个烹饪方法，一共烹饪了 $j$ 个菜，而且已经用食材 $x$ 烹饪了 $k$ 个菜，方案数是多少。为了能够转移 $f$，还需要预处理出每一行的 $a$ 之和。这样时间复杂度是 $\mathcal{O}(n^3m)$．

但是注意到最终统计答案的时候只关心 $k$ 是否大于等于 $(j-k)$，所以令 $f_{i,j}$ 为考虑前 $i$ 个烹饪方法，用食材 $x$ 烹饪的菜的个数，减去不用食材 $x$ 的菜的个数为 $j$，方案数是多少。这样复杂度就降到了 $\mathcal{O}(n^2m)$．Code．

ARC096E Everything on It

考虑将第二个容斥掉，枚举有 $1\sim i$ 出现次数 $\leq 1$ 次，剩余的无限制，假设其方案为 $f(i)$．

那么答案就是 $\sum f(i)(-1)^i\binom{n}{i}$．

考虑 $f(x)$ 怎么算，令 $y=n-x$，首先考虑不包含 $1\sim x$ 的子集一共有 $2^{2^y}$ 个，然后再考虑包含 $1\sim x$ 的子集，相当于将 $1\sim x$ 分成若干个不同的集合，每个集合从 $2^y$ 个集合中找一个集合，与其的并集构成一个新的集合。

令 $s_{i,j}$ 为将 $1\sim i$ 分成若 $j$ 个不同的集合的方案数（第二类斯特林数），枚举有 $1\sim x$ 中出现了的有 $i$ 个，一共分成 $j$ 个集合，那么就有：

$\begin{aligned} f(x)&=\sum_i\sum_j s_{i,j}({2^y})^j2^{2^y}\binom{x}{i} \\ &=2^{2^y}\sum_j (2^y)^j\sum_i \binom{x}{i}s_{i,j} \end{aligned}$

考虑后面那个求和号的组合意义，就是从 $x$ 个元素中选出 $i$ 个元素，再将这 $i$ 个元素划分成 $j$ 个集合。如果把没有选出的元素也看成一个集合，那么其就是 $x$ 个元素划分成 $(j+1)$ 个集合，其中有一个集合有标号且可空。所以：

$f(x)=2^{2^y}\sum_j (2^y)^j((j+1)s_{x,j+1}+s_{x,j})$

要注意 $2^{2^y}$ 计算时要将指数模 $M-1$．

Code．

「ZJOI2016」小星星

现在有大小均为 $n$ 的图 $A=(V,E_A)$ 和树 $B=(V,E_B)$，求符合条件的排列 $p$ 的个数，满足若 $(i,j)\in E_B$，则 $(p_i,p_j)\in E_A$．

比较容易理解的容斥，但并不是很容易想到要用容斥，要将什么条件容斥掉。

考虑一个暴力 dp，$f_{i,j,S}$ 考虑了 $B$ 中考虑 $i$ 的子树，点 $i$ 映射到了图中的点 $j$，已经被映射到的点集是 $S$．

暴力 dp 是 $\mathcal{O}(n^33^n)$，考虑到它的第三维是个子集卷积，难以优化，需要想办法规避掉子集卷积。

回想一下为什么要记录 $S$，在 dp 过程中可以枚举当前点映射到了哪个点，这样已经满足 $B$ 中每个点映射到了 $A$ 中的一个点，为了要满足映射到的点两两不同，即 $A$ 中的点都被映射到，所以需要记录 $S$．

那么就将这个容斥掉，枚举 $A$ 中一个集合 $S$，钦定这个 $S$ 中的点没有被映射到，方案数乘上容斥系数 $(-1)^{|S|}$ 求和即为答案。

枚举 $S$ 后，没有了“映射到的点两两不同”这个限制，于是乎可以直接 $f_{i,j}$ 为考虑子树 $i$，且点 $i$ 映射到了 $j$ 的方案数，容易做到总时间复杂度 $\mathcal{O}(n^3)$ dp．总的复杂度就是 $\mathcal{O}(2^nn^3)$．

虽然最终答案不会爆 long long，但是中间的 dp 可能会爆 long long，可以用 unsigned long long 直接自然溢出啥事没有，用 long long 的溢出似乎也能过，但是其实是 UB．Code．

「2021 山东三轮集训 Day2」体育测试

给定序列 $a$，求合法排列 $p$ 的方案数使得：

$a_i>0$，则满足 $i$ 在 $p$ 中出现位置 $\leq a_i$；

$a_i<0$，则满足 $i$ 在 $p$ 中出现位置 $\geq |a_i|$．

$n\leq 5000$，模 $10^9+7$．

首先考虑如果只有 $\leq$，将 $a$ 从小到大排序，那么方案数就是 $\prod (a_i-i+1)$．

但是现在有 $[\geq |a_i|]$，考虑将其容斥为 $(1-[\leq |a_i|-1])$．

具体地，枚举一个集合 $S$ 表示钦定这个集合内的 $\geq$ 强制钦定为不满足剩余的无限制，其容斥系数为 $(-1)^{|S|}$，将钦定不满足的 $\geq |a_i|$ 变为 $\leq |a_i|-1$，和其他的 $\leq$ 放在一起排序，求个 $\prod$，最后无限制的就是一个排列数。

根据这个容斥列 dp，设 $f_{i,j}$ 为考虑完了前 $i$ 个 $a$，钦定了 $j$ 个 $\geq$ 是不合法的，其带容斥系数的方案数是多少。$\leq$ 的正常转移，$\geq$ 转移的时候多带一个 $-1$ 的容斥系数。最后统计答案的时候将 $f_{n,i}(n-i)!$ 求和即为答案。Code ．

「HEOI2013」SAO

回忆一个外向树的拓扑序计数是如何解决的。对于所有的 $n!$ 种方案，必须要满足根在所有子孙的拓扑序之前，那么方案书就是 $\frac{n!}{\frac{n!}{(n-1)!}}=\frac{n!}{n}$，然后就可以剥去根不考虑根的印象。之后每次再考虑剩余若干子树的一个根 $x$，要满足 $x$ 出现在它所有子孙之前，那么方案数就会除掉 $siz_x$，之后 $x$ 就对总方案数没有了影响，可以剥除。所以外向树的拓扑序个数是 $\frac{n!}{\prod siz_x}$．

现在有了内向边，同时有内向边和外向边不是很好做，我们现在只会做只有外向边。

考虑容斥，选出 $i$ 条内向边，钦定它们是一定不满足的，剩余的内向边满足与否都无所谓。那么这种情况的方案数就是把选出的内向边看成外向边，其余的当作不存在（也就是这条边的限制满足与否都无所谓），然后对连通块分别求出拓扑序，再利用组合数乘起来（此时连通块之间不存在影响了），容斥系数就是 $(-1)^i$．

基于这个容斥，列出 dp，令 $g_{i,j}$ 表示考虑 $i$ 以内的子树，一共钦定了 $j$ 条内向边是不满足的。但是发现由于需要对拓扑序计数，还要记一个当前 $i$ 所在连通块的总和为 $k$，这样状态数就达到了 $\mathcal{O}(n^3)$，不能接受。

考虑我们最终只是想要求 $\sum g_{i,j,k}(-1)^j$，那么就可以令 $f_{i,k}=\sum g_{i,j,k}(-1)^j$，换而言之，令 $f_{i,k}$ 为考虑 $i$ 子树内，所有钦定方案的，带容斥系数的拓扑序数之和。转移即为一个树形背包，在钦定一条内向边一定不满足的时候，乘上一个 $-1$ 的容斥系数来转移即可。

时间复杂度 $\mathcal{O}(Tn^2)$．Code．