← 返回题目列表

Codeforces · 2029/H

H. 消息传播

中文机器翻译题面 查看原题

给定一个无向图,具有 $$$n$$$ 个顶点和 $$$m$$$ 个边。每条边连接两个顶点$$$(u, v)$$$,每天出现的概率为$$$\frac{p}{q}$$$。

最初,顶点 $$$1$$$ 有一条消息。归根结底,当且仅当该顶点本身或与其相邻的至少一个顶点在前一天收到消息时,该顶点才会收到消息。请注意,每天,每条边都会独立选择其外观。

计算所有顶点收到消息之前的预期天数,以 $$$998\,244\,353$$$ 为模。

输入

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

接下来是 $$$m$$$ 行,每行包含四个整数 $$$u$$$、$$$v$$$、$$$p$$$ 和 $$$q$$$ ($$$1\leq u\neq v\leq n$$$, $$$1\leq p<q<998\,244\,353$$$, $$$\gcd(p,q)=1$$$) — $$$u$$$ 和 $$$v$$$ 之间有一条无向边,每天出现的概率为 $$$\frac{p}{q}$$$。

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

输入中的附加约束:令 $$$g_{i,j}$$$ 为 $$$i$$$ 和 $$$j$$$ 之间出现边缘的概率(如果 $$$i$$$ 和 $$$j$$$ 之间没有边缘,$$$g_{i,j}=0$$$)。保证对于任何 $$$S\subseteq\{1,2,\ldots,n\}$$$ ($$$|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\,353$$$ 为模。

正式地,令 $$$M = 998\,244\,353$$$。可以证明,精确答案可以表示为不可约分数 $$$\frac{p}{q}$$$,其中 $$$p$$$ 和 $$$q$$$ 是整数,$$$q \not \equiv 0 \pmod{M}$$$。输出等于 $$$p \cdot q^{-1} \bmod M$$$ 的整数。换句话说,输出一个整数$$$x$$$,使得$$$0 \le x < M$$$ 且$$$x \cdot q \equiv p \pmod{M}$$$。

示例

输入 #1

2 1
1 2 1 10

输出 #1

10

输入 #2

3 3
1 2 1 2
1 3 1 2
2 3 1 2

输出 #2

887328316

输入 #3

1 0

输出 #3

0

输入#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

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

注意

在第一个测试中,答案等于图中唯一的边首次出现之前的预期天数,即 $$$\frac{1}{0.1}=10$$$。

在第二个测试中,在对 $$$998\,244\,353$$$ 取模之前,答案等于 $$$\frac{20}{9}$$$。

在第三个测试中,唯一的顶点已经有消息,所以答案是 $$$0$$$。