← 返回题目列表

Codeforces · 1842/H

H. Tenzing 和随机实数

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

存在 $$$n$$$ 0 到 1 之间的均匀随机实变量(含 0 和 1),分别表示为 $$$x_1, x_2, \ldots, x_n$$$。

丹增有 $$$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$$$。

示例

输入 #1

3 2
0 1 2
1 3 3

输出 #1

748683265

输入 #2

3 3
0 1 2
0 1 3
0 2 3

输出 #2

748683265

输入 #3

3 4
0 1 2
0 1 3
1 2 3
1 2 2

输出 #3

935854081

输入#4

4 4
0 1 2
0 3 4
1 1 3
1 2 4

输出#4

0

输入 #5

8 12
0 1 2
0 2 3
1 3 4
0 1 4
0 5 6
0 6 7
1 7 8
0 5 8
1 3 7
1 3 8
1 4 7
1 4 8

输出 #5

997687297

注意

在第一个测试用例中,条件为 $$$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$$$。