Студент готовится к олимпиаде и собирается решить $$$n$$$ задач. Сложность $$$i$$$-й задачи равна $$$a_i$$$.
Перед началом подготовки задачи случайно перемешиваются, после чего студент решает их в получившемся порядке. Каждая из $$$n!$$$ перестановок задач равновероятна. Изначально студент не помнит решений ни одной задачи.
Для каждой задачи $$$i$$$ также известно число $$$x_i$$$ — вероятность забыть решение задачи в процентах. Тогда $$$p_i = x_i / 100$$$ вероятность забыть решение $$$i$$$-й задачи.
Решая очередную задачу $$$i$$$, студент выполняет следующие действия:
— Решает задачу $$$i$$$ и запоминает её решение.
— Получает $$$1$$$ единицу опыта за каждую задачу $$$j$$$, решение которой он помнит и для которой $$$a_j \le a_i$$$.
— Для каждой задачи $$$j \ne i$$$, решение которой он помнит, с вероятностью $$$p_j$$$ он забывает её решение. Все такие события независимы.
Таким образом, студент не может забыть решение задачи сразу после её решения. Однако после решения каждой следующей задачи он может забыть её с вероятностью, соответствующей этой задаче. Если решение задачи забыто, то до конца подготовки студент его больше не помнит.
Найдите математическое ожидание количества опыта, которое будет получено.
В первой строке входных данных содержится единственное число $$$n$$$ $$$(1 \le n \le 3 \cdot 10^5)$$$ — количество задач.
В каждой из следующих $$$n$$$ строк содержатся два целых числа $$$a_i$$$ и $$$x_i$$$ $$$(1 \le a_i \le 10^9,\ 0 \le x_i \le 100)$$$ — сложность $$$i$$$-й задачи и число, задающее вероятность забыть её решение в процентах.
Значения $$$a_i$$$ не обязательно различны.
Можно показать, что математическое ожидание опыта представимо в виде несократимой дроби $$$\frac{p}{q}$$$, где $$$q$$$ не делится на $$$998244353$$$.
В единственной строке выведите одно число — значение $$$p \cdot q^{-1}$$$ по модулю $$$998244353$$$, где $$$q^{-1}$$$ — число, обратное к $$$q$$$ по модулю $$$998244353$$$.
33 506 1001 0
915057328
51 231 782 452 893 100
154133329
| Осенний кубок МИФИ 2026 |
|---|
| Закончено |
