题解：P6846 [CEOI 2019] Amusement Park

· · 题解

考虑一个 DAG 在边全部反转之后仍然会是 DAG，那么如果有一种反转 x 条边的方案，就一定有一种与之对应的反转另外 m - x 条边的方案。所以我们只需要求出总方案数，然后乘上 \dfrac{m}{2} 即可。

那么怎么求总方案数呢？

考虑状压 DP，设 f(S) 表示 S 点集的导出子图反转之后变成 DAG 的方案数。

我们知道 DAG 里一定有一些入度为 0 的点，删除这些入度为 0 的点后，我们会得到一个小的 DAG。考虑枚举这些入度为 0 的点，然后可以从小 DAG 转移。

枚举 S 的子集 T，将 S 拆成 T 和 S - T，当 T 是一个独立集的时候，f(S) 可以从 f(S - T) 转移而来。

但问题是这样做会算重复。比如我们枚举的一个合法的 T 是 0011，那么 0010 和 0001 一定也是合法的，这样同一种方案就被记重了。

考虑一个老生常谈的容斥，当 T 中点的个数是奇数个时，令它有 1 的贡献，当点的个数是偶数个时，令它有 -1 的贡献。

于是做完了，最终复杂度 O(3^n + n^22^n)。