题解：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)$。