#2540. 「PKUWC2018」随机算法

内存限制:512 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: l0nl1f3

题目描述

我们知道,求任意图的最大独立集是一类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 取模。

样例

样例输入

3 2
1 2
2 3

样例输出

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} ,保证给定的图没有重边和自环。