Имеется $$$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$$$. Другими словами, выведите такое целое число $$$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$$$).
Гарантируется, что все условия попарно различны.
Выведите вероятность того, что все условия выполнены, по модулю $$$M = 998~244~353$$$.
3 2 0 1 2 1 3 3
748683265
3 3 0 1 2 0 1 3 0 2 3
748683265
3 4 0 1 2 0 1 3 1 2 3 1 2 2
935854081
4 4 0 1 2 0 3 4 1 1 3 1 2 4
0
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
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$$$.
Название |
---|