#P17792. Message Spread

Message Spread

题目描述

给定一个无向图,包含 nn 个顶点和 mm 条边。每条边连接两个顶点 (u,v)(u, v),且每天出现的概率为 pq\frac{p}{q}。

初始时,顶点 11 拥有一条消息。每天结束时,某个顶点拥有消息,当且仅当它自己或与其相邻的至少一个顶点在前一天拥有消息。注意,每天每条边是否出现是独立选择的。

请计算所有顶点都拥有消息所需的期望天数,结果对 998 244 353998\,244\,353 取模。

输入格式

第一行包含两个整数 nn 和 mm(1≤n≤211\leq n\leq 21,n−1≤m≤n(n−1)2n-1\leq m\leq\frac{n(n-1)}{2})。

接下来 mm 行,每行包含四个整数 uu、vv、pp 和 qq(1≤u≠v≤n1\leq u\neq v\leq n,1≤p<q<998 244 3531\leq p<q<998\,244\,353,gcd⁡(p,q)=1\gcd(p,q)=1)——表示在 uu 和 vv 之间有一条无向边,每天出现的概率为 pq\frac{p}{q}。

保证图中没有自环或重边,并且如果所有边都出现时,图是连通的。

输入中还有一个额外约束:设 gi,jg_{i,j} 为 ii 和 jj 之间的边出现的概率(若无边则 gi,j=0g_{i,j}=0)。保证对于任意 S⊆{1,2,…,n}S\subseteq\{1,2,\ldots,n\}(∣S∣≥1|S|\ge 1),都有

$$\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}。$$

输出格式

输出一个整数,表示期望天数,对 998 244 353998\,244\,353 取模。

形式化地,设 M=998 244 353M=998\,244\,353。可以证明,答案可以表示为最简分数 pq\frac{p}{q},其中 pp 和 qq 是整数且 q≢0(modM)q\not\equiv0\pmod{M}。输出满足 0≤x<M0\le x<M 且 x⋅q≡p(modM)x\cdot q\equiv p\pmod{M} 的整数 xx。

输入输出样例 #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

说明/提示

在第一个测试点中,答案等于图中唯一一条边第一次出现所需的期望天数,即 10.1=10\frac{1}{0.1}=10。

在第二个测试点中,答案为 209\frac{20}{9},再对 998 244 353998\,244\,353 取模。

在第三个测试点中,唯一的顶点已经拥有消息,所以答案为 00。