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)。