PKUWC2019 D1T1

PKUWC2019 D1T1

不知道题目名

题面：

$n$ 个点，$m$ 条边的无向图，每条边可以存在/不存在，求在所有 $2^m$ 的状态中合法的拓扑序数量

$n \le 20,m \le \frac{n(n-1)}{2}$

Solution：

考虑 $2^{m}$ 的边的状态是没法做的，反向考虑每个点所能 “贡献" 的合法的边的状态

具体来说设 $dp_S$ 表示当前的拓扑序集合 $S$ 所能确定的边的状态，考虑加入新点 $x$ 使得 $S \rightarrow S'$

对于所有 $x$ 的入边 $(u,x)$ ，如果 $u \in S$ 那么这条边可存在也可不存在，否则必须不存在

这样就能更新能确定的边，最终答案是 $dp_{V}$

因为没地方交就不写了（也没啥好写的