CF1842H Tenzing and Random Real Numbers

有 $n$ 个在 $0$ 到 $1$ 之间（包含 $0$ 和 $1$）均匀分布的随机实数变量，分别记为 $x_1, x_2, \ldots, x_n$。 Tenzing 有 $m$ 个条件。每个条件的形式为 $x_i + x_j \le 1$ 或 $x_i + x_j \ge 1$。 Tenzing 想知道所有条件都被满足的概率，结果对 $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}$。

第一行包含两个整数 $n$ 和 $m$（$1 \le n \le 20$，$0 \le m \le n^2 + n$）。 接下来的 $m$ 行，每行包含三个整数 $t$、$i$ 和 $j$（$t \in \{0,1\}$，$1 \le i \le j \le n$）。 - 如果 $t=0$，该条件为 $x_i + x_j \le 1$。 - 如果 $t=1$，该条件为 $x_i + x_j \ge 1$。 保证所有条件两两不同。

输出所有条件都被满足的概率，对 $M = 998\,244\,353$ 取模。

在第一个测试用例中，条件为 $x_1 + x_2 \le 1$ 和 $x_3 + x_3 \ge 1$，每个条件被满足的概率都是 $\frac{1}{2}$，所以两个都满足的概率是 $\frac{1}{2} \cdot \frac{1}{2} = \frac{1}{4}$，对 $998\,244\,353$ 取模等于 $748683265$。 在第二个测试用例中，答案是 $\frac{1}{4}$。 在第三个测试用例中，答案是 $\frac{1}{16}$。 在第四个测试用例中，所有变量的和必须等于 $2$，所以概率为 $0$。 由 ChatGPT 4.1 翻译