Кости из Кошой-Коргона


Отправить решение Решать в редакторе

Сложность: 90%
Очки: 100 (частичный балл)
Ограничение по времени: 3.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

В крепости Кошой-Коргон археологи нашли n старинных игральных костей из кости и рога. Кости необычные: у кости i есть k[i] граней, и на гранях написаны неотрицательные числа v[i][1], …, v[i][k[i]] (числа на гранях могут повторяться). Каждая кость при броске выпадает любой гранью с одинаковой вероятностью 1 / k[i].

Все n костей бросают одновременно и складывают выпавшие числа. Учёным нужны q вероятностей: для каждого вопроса l r найдите вероятность того, что сумма окажется в пределах от l до r включительно.

Рисунок

Ответ — рациональное число P / Q; выведите P · Q⁻¹ по модулю 998244353.

Входные данные

В первой строке — числа n и q (1 ≤ n ≤ 2 · 10⁵, 1 ≤ q ≤ 10⁵). В каждой из следующих n строк описана кость: сначала k[i], затем k[i] чисел v[i][j] (1 ≤ k[i], 0 ≤ v[i][j]). Сумма всех k[i] и сумма наибольших чисел на костях Σ max_j v[i][j] не превосходят 2 · 10⁵. В каждой из следующих q строк — два целых числа l r (0 ≤ l ≤ r ≤ 10⁹).

Выходные данные

Для каждого вопроса выведите вероятность по модулю 998244353.

Пример 1

Вход:

2 3
2 0 1
6 1 2 3 4 5 6
7 7
1 7
0 3

Выход:

582309206
1
915057324

Пояснение

Первая кость — монета с числами 0 и 1, вторая — обычный кубик 1…6. Сумма равна 7 только при выпадении 1 и 6: вероятность 1/12. Сумма от 1 до 7 выпадает всегда.

Система оценивания

Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 20 % тестов сумма наибольших чисел на костях не больше 300.

Подсказка

Распределение суммы независимых величин — произведение их производящих многочленов; перемножать многочлены быстро помогает быстрое преобразование Фурье (по модулю 998244353 — его теоретико-числовой вариант).


Комментарии

Еще нет ни одного комментария.