自动搬运

查看原文

来自洛谷，原作者为

	Shattered_Shade 力

搬运于2025-08-24 22:24:32，当前版本为作者最后更新于2024-08-27 23:42:05，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

这篇题解主要补充一下容斥系数的比较笨的推导。

设 $f_s$ 为集合 $s$ 构成的子图的方案数，转移可以枚举 DAG 的入度为 0 的点，则有转移 $f_S=\sum_{T\subseteq S,T\neq \empty}g_T$，$g_T$ 为 $S$ 组成的 DAG 中入度为 0 的点集恰好为 $T$ 的方案数。

设 $w(S)=[S为独立集]$，则子集反演有

$$g_{T}=\sum_{T\subseteq H,H\subseteq S}(-1)^{|H|-|T|}f_{S/H}w(H) $$

其中 $f_{S/H}w(H)$ 为 DAG 中至少有 H 集合的点入度为 0 的方案数。

代回转移方程有

$$f_S=\sum_{T\subseteq S,T\neq\empty}\sum_{T\subseteq H,H\subseteq S}(-1)^{|H|-|T|}f_{S/H}w(H) $$

变换求和顺序枚举 H 有

$$f_S=\sum_{H\subseteq S,H\neq\empty}f_{S/H}w(H)(-1)^{|H|}\sum_{T\subseteq H,T\neq \empty}(-1)^{|T|} $$

同时有 $\sum_{T\subseteq H,T\neq \empty}(-1)^{|T|}=\sum_{i=1}^{|H|}{|H|\choose i}(-1)^i=-1$，代入即得

$$f_S=\sum_{H\subseteq S,H\neq\empty}f_{S/H}w(H)(-1)^{|H|+1} $$

这样就求出了容斥系数。