Refact.ai Match 1 (Codeforces Round 985) |
---|
Закончено |
Дан неориентированный граф с $$$n$$$ вершинами и $$$m$$$ рёбрами. Каждое ребро соединяет две вершины $$$(u, v)$$$ и каждый день появляется с вероятностью $$$\frac{p}{q}$$$.
Изначально в вершине $$$1$$$ есть сообщение. В конце дня вершина имеет сообщение тогда и только тогда, когда сама она или хотя бы одна из смежных с ней вершин имела сообщение в прошлый день. Обратите внимание, что каждый день ребро выбирает своё появление независимо.
Вычислите математическое ожидание количества дней, прежде чем все вершины получат сообщение, по модулю $$$998\,244\,353$$$.
Первая строка содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1\leq n\leq 21$$$, $$$n-1\leq m\leq\frac{n(n-1)}{2}$$$).
Затем следуют $$$m$$$ строк, каждая из которых содержит четыре целых числа $$$u$$$, $$$v$$$, $$$p$$$ и $$$q$$$ ($$$1\leq u\neq v\leq n$$$, $$$1\leq p<q<998\,244\,353$$$, $$$\gcd(p,q)=1$$$) — существует неориентированное ребро между вершинами $$$u$$$ и $$$v$$$, и оно каждый день появляется с вероятностью $$$\frac{p}{q}$$$.
Гарантируется, что в графе нет петель или кратных рёбер и что граф связен, если все рёбра появились.
Дополнительное ограничение на входные данные: Пусть $$$g_{i,j}$$$ — вероятность появления ребра между вершинами $$$i$$$ и $$$j$$$ ($$$g_{i,j}=0$$$, если между $$$i$$$ и $$$j$$$ нет ребра). Гарантируется, что для любого $$$S\subseteq\{1,2,\ldots,n\}$$$ ($$$|S|\ge 1$$$), $$$$$$ \prod_{i\in S}\left(\prod_{j\in\{1,2,\ldots,n\}\setminus S}(1-g_{i,j})\right)\not\equiv1\pmod{998\,244\,353}. $$$$$$
Выведите одно целое число в единственной строке вывода — математическое ожидание количества дней, по модулю $$$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}$$$.
2 11 2 1 10
10
3 31 2 1 21 3 1 22 3 1 2
887328316
1 0
0
5 81 2 1 111 3 2 111 4 3 111 5 4 112 4 5 112 5 6 113 4 7 114 5 8 11
469993557
21 221 2 3 42 3 4 53 4 5 65 6 7 86 7 8 97 8 9 108 9 2 39 10 3 410 11 4 511 12 5 612 13 6 713 14 7 814 15 8 915 16 9 1016 17 2 317 18 3 418 19 4 519 20 5 620 21 6 71 10 100 100115 4 147 2204 11 1 998244352
299529765
В первом тесте ответ равен математическому ожиданию количества дней, прежде чем появится единственное ребро в графе, и оно равно $$$\frac{1}{0.1}=10$$$.
Во втором тесте ответ равен $$$\frac{20}{9}$$$, прежде чем он будет взят по модулю $$$998\,244\,353$$$.
В третьем тесте единственная вершина уже имеет сообщение, поэтому ответ равен $$$0$$$.
Название |
---|