Codeforces Round 604 (Div. 1) |
---|
Закончено |
У Creatnx есть $$$n$$$ зеркал, пронумерованных от $$$1$$$ до $$$n$$$. Каждый день Creatnx спрашивает ровно одно зеркало «Красивый ли я?». $$$i$$$-е зеркало скажет Creatnx, что он красивый с вероятностью $$$\frac{p_i}{100}$$$ для всех $$$1 \le i \le n$$$.
Некоторые зеркала называются чекпойнтами. Изначально, только $$$1$$$-е зеркало является чекпойнтом. Это зеркало будет оставаться чекпойнтом все время.
Creatnx спрашивает зеркала одно за другим, начиная с $$$1$$$-о зеркала. Каждый день, если он спрашивает $$$i$$$-е зеркало, есть две возможности:
Иногда происходят следующие изменения: некоторые зеркала становятся чекпойнтами и некоторые зеркала перестают быть чекпойнтами. Вам дано $$$q$$$ запросов, каждый запрос задается номером зеркала $$$u$$$: если $$$u$$$-е зеркало не было чекпойнтом, тогда мы делаем его чекпойнтом. Иначе, $$$u$$$-е зеркало перестает быть чекпойнтом.
После каждого запроса, вам нужно посчитать математическое ожидание количества дней, до того как Creatnx станет счастливым.
Эти числа нужно найти по модулю $$$998244353$$$. Формально, пусть $$$M = 998244353$$$. Можно показать, что ответ может быть представлен в виде несократимой дроби $$$\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$$$, $$$q$$$ ($$$2 \leq n, q \le 2 \cdot 10^5$$$) — количество зеркал и запросов.
Во второй строке находится $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq 100$$$).
Каждая из следующих $$$q$$$ строк содержит единственное целое число $$$u$$$ ($$$2 \leq u \leq n$$$) — очередной запрос.
Выведите $$$q$$$ целых чисел — ответ на задачу после каждого запроса, взятый по модулю $$$998244353$$$.
2 2 50 50 2 2
4 6
5 5 10 20 30 40 50 2 3 4 5 3
117 665496274 332748143 831870317 499122211
В первом тесте после первого запроса, первое и второе зеркала являются чекпойнтами. Creatnx будет спрашивать первое зеркало, пока оно не скажет, что он красивый, после этого он будет спрашивать второе зеркало, пока оно не скажет, что он красивый, потому что оно является чекпойнтом. После этого он станет счастливым. Вероятности, что зеркала скажут, что он красивый равны $$$\frac{1}{2}$$$. Поэтому математическое ожидание количества дней, пока одно зеркало скажет, что он красивый равно $$$2$$$ и ответ равен $$$4 = 2 + 2$$$.
Название |
---|