Кости из Кошой-Коргона
В крепости Кошой-Коргон археологи нашли 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 — его теоретико-числовой вариант).
Комментарии