[PKUWC2018] 随机算法
题目描述
我们知道,求任意图的最大独立集是一类NP完全问题,目前还没有准确的多项式算法,但是有许多多项式复杂度的近似算法。
例如,小 C 常用的一种算法是:
1. 对于一个 $n$ 个点的无向图,先等概率随机一个 $1\ldots n$ 的排列 $p[1\ldots n]$。
2. 维护答案集合 $S$ ,一开始 $S$ 为空集,之后按照 $i=1\ldots n$ 的顺序,检查 $\{p[i]\}\cup S$ 是否是一个独立集,如果是的话就令 $S=\{p[i]\}\cup S$。
3. 最后得到一个独立集 $S$ 作为答案。
小 C 现在想知道,对于给定的一张图,这个算法的正确率,输出答案对 $998244353$ 取模。
输入输出格式
输入格式
第一行两个非负整数 $n,m$ 表示给定的图的点数和边数。
接下来 $m$ 行,每行有两个正整数 $(u,v) (u\neq v)$ 描述这张图的一条无向边。
输出格式
输出正确率,答案对 $998244353$ 取模。
输入输出样例
输入样例 #1
3 2
1 2
2 3
输出样例 #1
665496236
说明
#### 样例解释
这张图的最大独立集显然为 $2$,可以发现只有 $p[1]=2$ 时会得出 $S=\{2\}$,否则都是 $S=\{1,3\}$,所以答案是 $\frac{2}{3}$。
#### 数据范围
对于 $10\%$ 的数据,有$1\leq n\leq 9$。
对于 $30\%$ 的数据,有$1\leq n\leq 13$。
对于 $50\%$ 的数据,有$1\leq n\leq 17$。
另有 $10\%$ 的数据,满足给定的图是一条链。
另有 $10\%$ 的数据,满足给定的图是一棵树。
对于 $100\%$ 的数据,有$1\leq n\leq 20$,$0\leq m\leq \frac{n\times (n-1)}{2}$,保证给定的图没有重边和自环。