codeforces#P1842H. Tenzing and Random Real Numbers
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}$.
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.
Output the probability that all the conditions are satisfied, modulo $M = 998~244~353$.
Input
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.
Output
Output the probability that all the conditions are satisfied, modulo $M = 998~244~353$.
3 2
0 1 2
1 3 3
3 3
0 1 2
0 1 3
0 2 3
3 4
0 1 2
0 1 3
1 2 3
1 2 2
4 4
0 1 2
0 3 4
1 1 3
1 2 4
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
748683265
748683265
935854081
0
997687297
Note
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$.