题解：P6846 [CEOI2019] Amusement Park

· · 题解

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

设 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}

这样就求出了容斥系数。