310497: CF1842H. Tenzing and Random Real Numbers
Description
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 < M$ and $x \cdot q \equiv p \pmod{M}$.
InputThe 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.
OutputOutput the probability that all the conditions are satisfied, modulo $M = 998~244~353$.
ExamplesInput3 2 0 1 2 1 3 3Output
748683265Input
3 3 0 1 2 0 1 3 0 2 3Output
748683265Input
3 4 0 1 2 0 1 3 1 2 3 1 2 2Output
935854081Input
4 4 0 1 2 0 3 4 1 1 3 1 2 4Output
0Input
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 8Output
997687297Note
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$.
Input
题意翻译
有 $n$ 个 $[0,1]$ 范围内的均匀随机变量 $x_{1\cdots n}$ 和 $m$ 条限制，每条限制形如 $x_i+x_j\le 1$ 或 $x_i+x_j\ge 1$。请你求出所有限制均满足的概率。对 $998244353$ 取模。 $1\le n\le 20,\ 0\le m\le n^2+n$。Output
这个问题是关于计算满足一系列条件的概率。给定n个在0到1之间（包括0和1）均匀分布的随机实数变量，表示为x1, x2, ..., xn。Tenzing有m个条件，每个条件的形式为xi + xj ≤ 1或xi + xj ≥ 1。需要计算所有条件都满足的概率，结果对998,244,353取模。
输入数据格式：
第一行包含两个整数n和m（1≤n≤20，0≤m≤n^2+n）。
接下来m行，每行包含三个整数t, i和j（t ∈ {0,1}，1≤i≤j≤n）。
- 如果t=0，条件是xi + xj ≤ 1。
- 如果t=1，条件是xi + xj ≥ 1。
保证所有条件都是两两不同的。
输出数据格式：
输出一个整数，表示所有条件都满足的概率，对M = 998,244,353取模。
请注意，上述内容是对原题目的一种解释和概述，具体的题目条件和要求可能会有更详细的规定。题目大意： 这个问题是关于计算满足一系列条件的概率。给定n个在0到1之间（包括0和1）均匀分布的随机实数变量，表示为x1, x2, ..., xn。Tenzing有m个条件，每个条件的形式为xi + xj ≤ 1或xi + xj ≥ 1。需要计算所有条件都满足的概率，结果对998,244,353取模。 输入数据格式： 第一行包含两个整数n和m（1≤n≤20，0≤m≤n^2+n）。 接下来m行，每行包含三个整数t, i和j（t ∈ {0,1}，1≤i≤j≤n）。 - 如果t=0，条件是xi + xj ≤ 1。 - 如果t=1，条件是xi + xj ≥ 1。 保证所有条件都是两两不同的。 输出数据格式： 输出一个整数，表示所有条件都满足的概率，对M = 998,244,353取模。 请注意，上述内容是对原题目的一种解释和概述，具体的题目条件和要求可能会有更详细的规定。