CF1842H.Tenzing and Random Real Numbers

There are $n$ uniform random real variables between 0 and 1, inclusive, which are denoted as $x_1, x_2, \ldots, x_n$.

Tenzing has $m$ conditions. Each condition has the form of $x_i+x_j\le 1$ or $x_i+x_j\ge 1$.

Tenzing wants to know the probability that all the conditions are satisfied, modulo $998~244~353$.

Formally, let $M = 998~244~353$. It can be shown that the answer can be expressed as an irreducible fraction $\frac{p}{q}$, where $p$ and $q$ are integers and $q \not \equiv 0 \pmod{M}$. Output the integer equal to $p \cdot q^{-1} \bmod M$. In other words, output the integer $x$ that $0 \le x \lt M$ and $x \cdot q \equiv p \pmod{M}$.

有 $n$ 个在区间 $[0,1]$ 上独立均匀分布的实随机变量，记为 $x_1, x_2, \ldots, x_n$。

丹增提出了 $m$ 个约束条件。每个约束形如 $x_i + x_j \le 1$ 或 $x_i + x_j \ge 1$。

丹增希望知道所有约束同时被满足的概率，结果对 $998~244~353$ 取模。

形式化地，令 $M = 998~244~353$。可以证明该概率可表示为既约分数 $\frac{p}{q}$，其中 $p$ 和 $q$ 为整数，且 $q \not \equiv 0 \pmod{M}$。请输出整数 $p \cdot q^{-1} \bmod M$。换言之，输出满足 $0 \le x < M$ 且 $x \cdot q \equiv p \pmod{M}$ 的整数 $x$。

The first line contains two integers $n$ and $m$ ($1\le n\le 20$, $0\le m\le n^2+n$).

Then following $m$ lines of input contains three integers $t$, $i$ and $j$ ($t \in {0,1}$, $1\le i\le j\le n$).

• If $t=0$, the condition is $x_i+x_j\le 1$.
• If $t=1$, the condition is $x_i+x_j\ge 1$.

It is guaranteed that all conditions are pairwise distinct.

第一行包含两个整数 $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$。

保证所有约束条件两两互不相同。

Output the probability that all the conditions are satisfied, modulo $M = 998~244~353$.

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

In the first test case, the conditions are $x_1+x_2 \le 1$ and $x_3+x_3\ge 1$, and the probability that each condition is satisfied is $\frac 12$, so the probability that they are both satisfied is $\frac 12\cdot \frac 12=\frac 14$, modulo $998~244~353$ is equal to $748683265$.

In the second test case, the answer is $\frac 14$.

In the third test case, the answer is $\frac 1{16}$.

In the fourth test case, the sum of all variables must equal $2$, so the probability is $0$.

在第一个测试用例中，约束条件为 $x_1+x_2 \le 1$ 和 $x_3+x_3\ge 1$，每个约束条件被满足的概率均为 $\frac 12$，因此两个约束条件同时被满足的概率为 $\frac 12\cdot \frac 12=\frac 14$，对 $998~244~353$ 取模的结果为 $748683265$。

在第二个测试用例中，答案为 $\frac 14$。

在第三个测试用例中，答案为 $\frac 1{16}$。

在第四个测试用例中，所有变量之和必须等于 $2$，因此概率为 $0$。