#P17792. Message Spread
Message Spread
题目描述
给定一个无向图,包含 个顶点和 条边。每条边连接两个顶点 ,且每天出现的概率为 。
初始时,顶点 拥有一条消息。每天结束时,某个顶点拥有消息,当且仅当它自己或与其相邻的至少一个顶点在前一天拥有消息。注意,每天每条边是否出现是独立选择的。
请计算所有顶点都拥有消息所需的期望天数,结果对 取模。
输入格式
第一行包含两个整数 和 (,)。
接下来 行,每行包含四个整数 、、 和 (,,)——表示在 和 之间有一条无向边,每天出现的概率为 。
保证图中没有自环或重边,并且如果所有边都出现时,图是连通的。
输入中还有一个额外约束:设 为 和 之间的边出现的概率(若无边则 )。保证对于任意 (),都有
$$\prod_{i\in S}\left(\prod_{j\in\{1,2,\ldots,n\}\setminus S}(1-g_{i,j})\right)\not\equiv1\pmod{998\,244\,353}。$$输出格式
输出一个整数,表示期望天数,对 取模。
形式化地,设 。可以证明,答案可以表示为最简分数 ,其中 和 是整数且 。输出满足 且 的整数 。
输入输出样例 #1
输入 #1
2 1
1 2 1 10
输出 #1
10
输入输出样例 #2
输入 #2
3 3
1 2 1 2
1 3 1 2
2 3 1 2
输出 #2
887328316
输入输出样例 #3
输入 #3
1 0
输出 #3
0
输入输出样例 #4
输入 #4
5 8
1 2 1 11
1 3 2 11
1 4 3 11
1 5 4 11
2 4 5 11
2 5 6 11
3 4 7 11
4 5 8 11
输出 #4
469993557
输入输出样例 #5
输入 #5
21 22
1 2 3 4
2 3 4 5
3 4 5 6
5 6 7 8
6 7 8 9
7 8 9 10
8 9 2 3
9 10 3 4
10 11 4 5
11 12 5 6
12 13 6 7
13 14 7 8
14 15 8 9
15 16 9 10
16 17 2 3
17 18 3 4
18 19 4 5
19 20 5 6
20 21 6 7
1 10 100 1001
15 4 147 220
4 11 1 998244352
输出 #5
299529765
说明/提示
在第一个测试点中,答案等于图中唯一一条边第一次出现所需的期望天数,即 。
在第二个测试点中,答案为 ,再对 取模。
在第三个测试点中,唯一的顶点已经拥有消息,所以答案为 。