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<q<998\,244\,353$，$\gcd(p,q)=1$）——表示在 $u$ 和 $v$ 之间有一条无向边，每天出现的概率为 $\frac{p}{q}$。

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

输入中还有一个额外约束：设 $g_{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\equiv0\pmod{M}$。输出满足 $0\le x<M$ 且 $x\cdot q\equiv p\pmod{M}$ 的整数 $x$。

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

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

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

由 ChatGPT 4.1 翻译