[Solution] Cross Xor solution codeforces

Cross Xor solution codeforces – 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 𝑎𝑖,𝑗ai,j written on it. Initially, all elements are set to 00.

[Solution] Cross Xor solution codeforces

We are allowed to do the following operation:

  • Choose indices 1𝑖𝑟1≤i≤r and 1𝑗𝑐1≤j≤c, then replace all values on the same row or column as (𝑖,𝑗)(i,j) with the value xor 11. In other words, for all 𝑎𝑥,𝑦ax,y where 𝑥=𝑖x=i or 𝑦=𝑗y=j or both, replace 𝑎𝑥,𝑦ax,y with 𝑎𝑥,𝑦ax,y xor 11.

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𝑘2k 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 00. As this number can be large, output it modulo 998244353998244353.

Input

The first line contains two integers 𝑟r and 𝑐c (1𝑟,𝑐20001≤r,c≤2000)  — the number of rows and columns of the grid respectively.

The 𝑖i-th of the next 𝑟r lines contain 𝑐c characters 𝑏𝑖,1,𝑏𝑖,2,,𝑏𝑖,𝑐bi,1,bi,2,…,bi,c (𝑏𝑖,𝑗{0,1,?}bi,j∈{0,1,?}).

[Solution] Cross Xor solution codeforces

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

Examples
input

Copy
3 3
?10
1??
010
output

Copy
1
input

Copy
2 3
000
001

[Solution] Cross Xor solution codeforces

output

Copy
0
input

Copy
1 1
?
output

Copy
2
input

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

Copy
8

Cross Xor solution codeforces

In the first test case, the only way to fill in the ??s is to fill it in as such:

0 1 0
1 1 1
0 1 0

This can be accomplished by doing a single operation by choosing (𝑖,𝑗)=(2,2)(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.

 

For Solution

Click here

Leave a Comment