Известный конкурс программирования Forcedeltas включает $$$n$$$ участников, $$$m$$$ задач и длится $$$k$$$ минут.
Для каждого участника $$$i$$$ и каждой задачи $$$j$$$ известно целое число $$$a_{i, j}$$$. Если $$$a_{i, j} = 0$$$, это означает, что участник $$$i$$$ не может решить задачу $$$j$$$. В противном случае, это означает, что участник $$$i$$$ может решить задачу $$$j$$$ за ровно $$$a_{i, j}$$$ минут.
Все участники будут следовать одной стратегии. Конкретно, каждый участник составит список всех задач, которые он может решить, перемешает список равномерно случайным образом и будет решать задачи в том порядке, пока список не закончится или конкурс не закончится.
Например, если список для участника $$$i$$$ выглядит как $$$j_1, j_2, \ldots$$$ после перемешивания, то он решит задачу $$$j_1$$$ в минуту $$$a_{i, j_1}$$$, задачу $$$j_2$$$ в минуту $$$a_{i, j_1} + a_{i, j_2}$$$ и так далее. Обратите внимание, что ни одна задача не может быть решена в минуту $$$k + 1$$$ или позже.
Мы скажем, что участник $$$i$$$ получает награду Первый, кто решит за задачу $$$j$$$, если никакой другой участник не решит задачу $$$j$$$ строго раньше. В частности, это означает, что несколько участников могут получить награду за одну и ту же задачу.
Найдите ожидаемое количество наград, которое каждый участник получит, по модулю $$$998\,244\,353$$$ (см. раздел "Вывод" для подробностей).
Первая строка содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ — количество участников, количество задач и длительность конкурса в минутах ($$$1 \le n \le 500$$$; $$$1 \le m \le 26$$$; $$$1 \le k \le 300$$$).
$$$i$$$-я из следующих $$$n$$$ строк содержит $$$m$$$ целых чисел $$$a_{i, 1}, a_{i, 2}, \ldots, a_{i, m}$$$ ($$$0 \le a_{i, j} \le k$$$). $$$j$$$-е из этих чисел обозначает количество минут, необходимых участнику $$$i$$$ для решения задачи $$$j$$$, или $$$0$$$, если участник $$$i$$$ не может решить задачу $$$j$$$.
Выведите $$$n$$$ целых чисел — ожидаемое количество наград, которые получат участники $$$1, 2, \ldots, n$$$, по модулю $$$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 \lt M$$$ и $$$x \cdot q \equiv p \pmod{M}$$$.
5 3 60 30 0 0 40 20 0 30 60 0 0 0 0 60 60 1
1 1 249561089 0 499122177
В тестовом примере участник $$$1$$$ всегда получает награду за задачу $$$1$$$, участник $$$2$$$ всегда получает награду за задачу $$$2$$$, ожидаемое количество наград, которое получит участник $$$3$$$, равно $$$\frac{3}{4}$$$, участник $$$4$$$ никогда не получает наград, и ожидаемое количество наград, которое получит участник $$$5$$$, равно $$$\frac{1}{2}$$$.
| 2021-2022 ICPC NERC (NEERC), North-Western Russia Regional Contest (Northern Subregionals) |
|---|
| Закончено |
