Codeforces Global Round 20 |
---|
Закончено |
Дана таблица с $$$r$$$ строк и $$$c$$$ столбцов, где в клетке на пересечении $$$i$$$-й строки и $$$j$$$-го столбца записано целое число $$$a_{i, j}$$$. Изначально все элементы равны $$$0$$$. Мы можем выполнять следующую операцию:
Вы хотите получить таблицу $$$b$$$, проделав вышеописанные операции конечное число раз. Однако, некоторые элементы $$$b$$$ отсутствуют и заменены на '?'.
Пусть $$$k$$$ — количество символов '?'. Среди всех $$$2^k$$$ способов заполнения таблицы $$$b$$$ путем замены каждого '?' на '0' или '1', подсчитайте количество таблиц, которые могут быть получены путем выполнения этой операции конечное число раз, начиная с таблицы, заполненной $$$0$$$. Поскольку это число может быть большим, выведите его по модулю $$$998244353$$$.
Первая строка содержит два целых числа $$$r$$$ и $$$c$$$ ($$$1 \le r, c \le 2000$$$) — количество строк и столбцов таблицы соответственно.
$$$i$$$-я из следующих $$$r$$$ строк содержит $$$c$$$ символов $$$b_{i, 1}, b_{i, 2}, \ldots, b_{i, c}$$$ ($$$b_{i, j} \in \{0, 1, ?\}$$$).
Выведите одно целое число, представляющее количество способов заполнения таблицы $$$b$$$ по модулю $$$998244353$$$.
3 3 ?10 1?? 010
1
2 3 000 001
0
1 1 ?
2
6 9 1101011?0 001101?00 101000110 001011010 0101?01?? 00?1000?0
8
В первом примере единственный способ заполнить $$$\texttt{?}$$$ — это заполнить так:
0 | 1 | 0 |
1 | 1 | 1 |
0 | 1 | 0 |
Этого можно добиться, выполнив одну операцию, выбрав $$$(i,j)=(2,2)$$$.
Во втором примере можно показать, что не существует последовательности операций, которые могут создать такую таблицу.
Название |
---|