P6846 [CEOI 2019] Amusement Park

题目描述

有一个含 $n$ 个点,$m$ 条边的有向图,图无重边,无自环,两点之间不成环。 现在我们想改变一些边的方向,使得该有向图无环。 您需要求出,每一种改变方向后使得该有向图无环的方案的需改变边的数量之和 $\bmod\ 998244353$ 之后的答案。

输入格式

输出格式

说明/提示

#### 样例解释 #### 样例 1 解释 有如下两种方案: - 改变方向。 - 不改变方向。 所以输出 $1+0=1$。 #### 样例 2 解释 共有六种可行的方案: - $1\to2,2\to3,1\to3$ - $1\to2,3\to2,1\to3$ - $1\to2,3\to2,3\to1$ - $2\to1,2\to3,1\to3$ - $2\to1,2\to3,3\to1$ - $2\to1,3\to2,3\to1$ 所以输出 $0+1+2+1+2+3=9$。 #### 数据范围 对于 $100\%$ 的数据,保证 $1\le n\le 18$,$0\le m\le \frac{n\times (n-1)}{2}$,$1\le a_i,b_i\le n$,$a_i\not=b_i$,对于 $i\not=j$,均有 $a_i\not=a_j$ 或者 $b_i\not=b_j$,无序数对 $\{a_i,b_i\}$ 互不相同。 详细子任务限制及分值如下表: | 子任务编号 | 限制 | 分值 | | :-: |:-:|:-:| | 1 | $n\le 3$ | $7$ | | 2 | $n\le 6$ | $12$ | | 3 | $n\le 10$ | $23$ | | 4 | $n\le 15$ | $21$ | | 5 | 无特殊限制 | $37$ | #### 说明 本题译自 [Central-European Olympiad in Informatics 2019](https://ceoi.sk/) [Day 2](https://ceoi.sk/tasks/) [T1 Amusement Park](https://ceoi.sk/static/statements/amusementpark-ENG.pdf)。