Cross Xor

题意翻译

对于一个 $n\times m$ 的 `01` 矩阵，每次【操作】可以把一个元素 $(i,j)$ 和与它同行或同列的所有格子一起取反。 给定一个由 `01?` 构成的 $n\times m$ 矩阵，问有多少种将 `?` 替换为 `0` 或 `1` 的方案使得此矩阵可以通过上述操作消成全 `0` 的矩阵。

题目描述

There is a grid with $ r $ rows and $ c $ columns, where the square on the $ i $ -th row and $ j $ -th column has an integer $ a_{i, j} $ written on it. Initially, all elements are set to $ 0 $ . We are allowed to do the following operation: - Choose indices $ 1 \le i \le r $ and $ 1 \le j \le c $ , then replace all values on the same row or column as $ (i, j) $ with the value xor $ 1 $ . In other words, for all $ a_{x, y} $ where $ x=i $ or $ y=j $ or both, replace $ a_{x, y} $ with $ a_{x, y} $ xor $ 1 $ . You want to form grid $ b $ by doing the above operations a finite number of times. However, some elements of $ b $ are missing and are replaced with '?' instead. Let $ k $ be the number of '?' characters. Among all the $ 2^k $ ways of filling up the grid $ b $ by replacing each '?' with '0' or '1', count the number of grids, that can be formed by doing the above operation a finite number of times, starting from the grid filled with $ 0 $ . As this number can be large, output it modulo $ 998244353 $ .

输入输出格式

输入格式

The first line contains two integers $ r $ and $ c $ ( $ 1 \le r, c \le 2000 $ ) — the number of rows and columns of the grid respectively. The $ i $ -th of the next $ r $ lines contain $ c $ characters $ b_{i, 1}, b_{i, 2}, \ldots, b_{i, c} $ ( $ b_{i, j} \in \{0, 1, ?\} $ ).

输出格式

Print a single integer representing the number of ways to fill up grid $ b $ modulo $ 998244353 $ .

输入输出样例

输入样例 #1

3 3
?10
1??
010

输出样例 #1

1

输入样例 #2

2 3
000
001

输出样例 #2

0

输入样例 #3

1 1
?

输出样例 #3

2

输入样例 #4

6 9
1101011?0
001101?00
101000110
001011010
0101?01??
00?1000?0

输出样例 #4

8

说明

In the first test case, the only way to fill in the $ \texttt{?} $ s is to fill it in as such: 010111010This can be accomplished by doing a single operation by choosing $ (i,j)=(2,2) $ . In the second test case, it can be shown that there is no sequence of operations that can produce that grid.