CF2029H Message Spread

给定一个无向图，包含 $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

输出一个整数，表示期望天数，对 $998\,244\,353$ 取模。 形式化地，设 $M=998\,244\,353$。可以证明，答案可以表示为最简分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 是整数且 $q\not\equiv0\pmod{M}$。输出满足 $0\le x

在第一个测试点中，答案等于图中唯一一条边第一次出现所需的期望天数，即 $\frac{1}{0.1}=10$。 在第二个测试点中，答案为 $\frac{20}{9}$，再对 $998\,244\,353$ 取模。 在第三个测试点中，唯一的顶点已经拥有消息，所以答案为 $0$。 由 ChatGPT 4.1 翻译