图计数类问题·典

标签：DAG cdot 出度 点集 问题 计数 mathcal oplus

一、无向图定向

问题描述：给定一张 \(n\) 个点，\(m\) 条边的的无向图，求给每条边定向后是 DAG 的方案数，对 \(998244353\) 取模。

数据范围：\(1 \le n \le 20\)。

设 \(f_S\) 表示 \(S\) 点集中的点在 DAG 上时的方案数，枚举出度为 \(0\) 的点集 \(T\)，\(g(S)\) 表示 \(S\) 能否成为出度为 \(0\) 的点集，当且仅当 \(S\) 内没有边时为 \(1\)，否则为 \(0\)。

\[f_S = \sum_{T \subseteq S, T \neq \varnothing} f_{S \oplus T} \cdot (-1) ^ {|T| - 1} \cdot g(T) \times 2 ^ {(S \oplus T) 和 T 之间边的数量} \]

直接做是 \(\mathcal{O}(3 ^ n)\)，利用子集卷积可以做到 \(\mathcal{O}(2 ^ n \cdot n ^ 2)\)。

标签：DAG,cdot,出度,点集,问题,计数,mathcal,oplus
From： https://www.cnblogs.com/FidoPuppy/p/17548802.html