#1979. 胡策的统计
胡策的统计
胡策的统计
题目描述
标题: 胡策的统计 - Problem - QOJ.ac
#4259. 胡策的统计
The problem was used in the following contests:
在 OI 界,有一位无人不知无人不晓,OI 水平前无古人后无来者的胡策,江湖人称一眼秒题胡大爷!
今天胡策在研究无向图的连通性。对于一个无向图定义它的连通值为该图连通块数的阶乘。
为了研究连通值的性质,胡策随手画了一个 n 个结点的简单无向图 G,结点分别编号为 1,…,n,他想统计出 G 的所有生成子图的连通值之和。
胡策当然会做啦!但是他想考考你。你只用输出结果对 998244353 (7×17×223+1,一个质数) 取模后的结果。
简单无向图即无重边无自环的无向图。生成子图即原图中删去若干条边(可以是 0 条)后形成的图。
输入格式
第一行两个整数 n,m,表示 G 的结点数和边数。保证 n≥1,m≥0。
接下来 m 行,每行两个整数 v,u,表示 v 号结点和 u 号结点之间有一条无向边。保证 1≤v,u≤n,保证没有重边和自环。
输出格式
一行,一个整数表示答案。
样例一
input
6 13
1 2
1 3
2 3
1 4
4 2
3 4
5 2
3 5
5 4
6 2
6 3
6 4
6 5
output
16974
样例二
见样例数据下载。
限制与约定
测试点编号 n 特殊限制 1≤6无2≤1034≤17567≤20G 为完全图8无910
**时间限制:**3s
**空间限制:**256MB
来源
中国国家集训队互测2015 - By 吕凯风
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
6 13
1 2
1 3
2 3
1 4
4 2
3 4
5 2
3 5
5 4
6 2
6 3
6 4
6 5
16974
样例 2
20 153
2 1
2 3
4 1
4 2
5 1
5 3
5 4
6 1
4 6
7 1
7 2
3 7
4 7
5 7
6 7
1 8
2 8
3 8
4 8
8 5
6 8
7 8
9 1
5 9
9 7
8 9
10 1
2 10
10 3
10 5
10 6
7 10
10 9
11 2
3 11
11 6
7 11
8 11
9 11
10 11
1 12
12 2
3 12
12 4
6 12
7 12
12 8
12 9
12 10
12 11
1 13
2 13
3 13
13 4
13 5
13 6
8 13
13 9
10 13
13 11
13 12
14 1
14 2
14 3
4 14
14 6
14 8
14 9
10 14
14 12
15 1
2 15
15 3
15 4
5 15
6 15
15 7
8 15
9 15
15 10
11 15
15 12
1 16
2 16
16 3
16 4
6 16
16 7
16 8
16 9
10 16
16 12
16 13
16 15
1 17
2 17
4 17
17 6
17 9
10 17
11 17
17 12
13 17
17 14
15 17
16 17
18 1
18 2
3 18
18 4
18 5
6 18
7 18
8 18
18 9
18 10
18 11
12 18
13 18
18 15
18 17
1 19
19 2
3 19
19 4
5 19
19 6
19 7
8 19
10 19
11 19
19 12
13 19
19 14
19 15
19 17
19 18
20 1
20 2
3 20
20 5
6 20
7 20
8 20
20 9
10 20
20 11
12 20
20 14
15 20
20 17
20 18
20 19
373721579