Determining which Grids are Obtainable
Let $$$R_i$$$ and $$$C_j$$$ denote $$$\bigotimes\limits_{j=1}^c a_{i,j}$$$ and $$$\bigotimes\limits_{i=1}^r a_{i,j}$$$ respectively, or the xor-sum of the $$$i$$$-th row and the xor-sum of the $$$j$$$-th column respectively.
We will split the problem into 3 cases.
Case 1: $$$r$$$ is even and $$$c$$$ is even
Choose some $$$(x,y)$$$ and do an operation on all $$$(i,j)$$$ where $$$i=x$$$ or $$$j=y$$$. The effect of this series of operations is toggling $$$(x,y)$$$.
All possible grids are reachable. Counting them is easy.
Case 2: $$$r$$$ is even and $$$c$$$ is odd
If $$$r$$$ is odd and $$$c$$$ is even, we can treat it as the same case by swapping a few variables.
Notice that every operation toggles all elements in $$$R$$$. It is neccasary that $$$R$$$ all values in R are the same, let us prove that this is sufficient as well.
Now suppose $$$R$$$ is all 0. If $$$R$$$ is all $$$1$$$. We can perform the operation on $$$(1,1)$$$ and now $$$R$$$ is all $$$0$$$.
If we pick $$$1 \leq x \leq r$$$ and $$$1 \leq y < c$$$ and perform operations on all $$$(i,j)$$$ where $$$i \neq x$$$ and $$$j=y$$$ or $$$j=c$$$, then it is equivalent to toggling $$$(x,y)$$$ and $$$(x,c)$$$.
We can perform the following new operation:
- pick $$$1 \leq x \leq r$$$ and $$$1 \leq y < c$$$
- toggle $$$(x,y)$$$,$$$(x,c)$$$
Since $$$R$$$ is all 0, each row has an even number of $$$1$$$. If we apply the new operation on all $$$(x,y)$$$ where $$$a_{x,y} = 1$$$ and $$$y < c$$$, then $$$(x,c)$$$ will be $$$0$$$ in the end. Hence, the whole grid will be $$$0$$$.
Case 3: $$$r$$$ is odd and $$$c$$$ is odd
Notice that every operation toggles all elements in $$$R$$$ and $$$C$$$. It is neccasary that both $$$R$$$ are $$$C$$$ all having the same values, let us prove that this is sufficient as well.
Suppose $$$R$$$ is all $$$0$$$ and $$$C$$$ is all $$$0$$$. If $$$R$$$ and $$$C$$$ are all $$$1$$$, we apply the operation on $$$(1,1)$$$ to make $$$R$$$ and $$$C$$$ both all $$$0$$$
Notice that if we pick $$$1 \leq x_1 < x_2 \leq r$$$ and $$$1 \leq y_1 < y_2 \leq c$$$. Let $$$S=\{(x_1,y_1), (x_1,y_2), (x_2,y_1),(x_2,y_2)\}$$$. When we perform operations on all cells in $$$S$$$, it is equivalent to toggling all cells in $$$S$$$.
We can perform the following new operation:
- pick $$$1 \leq x < r$$$ and $$$1 \leq y < c$$$
- toggle $$$(x,y)$$$,$$$(x,c)$$$,$$$(r,y)$$$,$$$(r,c)$$$
Since $$$R$$$ and $$$C$$$ is all 0, each row and column has an even number of 1. If we apply the new operation on all $$$(x,y)$$$ where $$$a_{x,y} = 1$$$ and $$$x < r$$$ and $$$y < c$$$ , then $$$(x,c)$$$ will be $$$0$$$ for $$$0 < x < r$$$ and $$$(r,y)$$$ will be $$$0$$$ for $$$0 < y < c$$$ in the end. And hence, $$$a_{r,c} = 0$$$ too since $$$R$$$ and $$$C$$$ is all 0. Hence, the whole grid will be $$$0$$$.
Alternate Justification
Thanks to dario2994 for writing this.
Let $$$V = Z_2^{nm}$$$. $$$V$$$ is endowed with the natural scalar product, which induces the concept of orthogonality.
Let $$$M$$$ be the subspace generated by the moves. Let $$$M^{\perp}$$$ be the space orthogonal to $$$M$$$. It is a basic result in linear algebra that $$$(M^{\perp})^{\perp} = M$$$.
One can see that $$$\{(x1, y1), (x1, y2), (x2, y1), (x2, y2)\}$$$ belongs to $$$M$$$ (it is a combination of 4 moves). Thus one deduces that if $$$u \in M^{\perp}$$$ then $$$u_{x,y} = a_x \oplus b_y$$$ for two vectors $$$a\in Z_2^r, b \in Z_2^c$$$. Given $$$a, b$$$; the scalar product between $$$u$$$ and the move centered at $$$(x, y)$$$ is: $$$xor(a) \oplus xor(b) \oplus (c+1)a_x \oplus (r+1)b_y$$$. Assume that $$$u$$$ is in $$$M^{\perp}$$$:
- If $$$r, c$$$ are both even, then $$$a_x$$$ and $$$b_y$$$ must be constant and equal each other. Thus $$$M^{\perp}$$$ is only the $$$0$$$ vector.
- If $$$r$$$ is even and $$$c$$$ is odd, then $$$b_y$$$ is constant. Hence $$$M^{\perp}$$$ is generated by any two rows.
- If $$$r$$$ is odd and $$$c$$$ is even, analogous.
- If $$$r$$$ and $$$c$$$ are both odd, then the only condition is $$$xor(a) \oplus xor(b) = 0$$$. This is necessary and sufficient for the orthogonality. And it implies that $$$M^{\perp}$$$ is generated by any two rows and any two columns.
Since we determined $$$M^{\perp}$$$, we have determined also $$$M$$$.
Counting
Case 1 and 2 are the easy cases while counting case 3 is more involved.
Case 1: $$$r$$$ is even and $$$c$$$ is even
All grids are obtainable. Let $$$\#?$$$ denote the number of $$$\texttt{?}$$$s in the grid. Then the answer is $$$2^{\#?}$$$ since all grid are obtainable.
Case 2: $$$r$$$ is even and $$$c$$$ is odd
If $$$r$$$ is odd and $$$c$$$ is even, we can treat it as the same case by swapping a few variables.
Let us fix whether we want $$$R=[0,0,\ldots,0]$$$ or $$$R=[1,1,\ldots,1]$$$. We will count the number of valid grids for each case.
Let $$$\#?_i$$$ denote the number of $$$\texttt{?}$$$s in the $$$i$$$-th row. If $$$\#?_i>0$$$, then then number of ways to set the $$$i$$$-th row is $$$2^{\#?_i-1}$$$. Otherwise, the number of ways is either $$$0$$$ to $$$1$$$ depending on the initial value of $$$R_i$$$.
Case 3: $$$r$$$ is odd and $$$c$$$ is odd
Let us define a bipartite graph with vertices $$$r+c$$$ vertices, labelled $$$V_{R,i}$$$ for $$$1 \leq i \leq r$$$ and $$$V_{C,j}$$$ for $$$1 \leq j \leq c$$$. If $$$a_{i,j}=\texttt{?}$$$, then we will add an (undirected) edge $$$V_{R,i} \leftrightarrow V_{C,j}$$$. Now we assume that each $$$\texttt{?}$$$ is set to $$$\texttt{0}$$$ at first. We will choose a subset of them to turn into $$$\texttt{1}$$$. When we do this on $$$a_{i,j}$$$, the value of $$$R_i$$$ and $$$C_j$$$ will toggle. In terms of the graph, this corresponds to assigning $$$0$$$ or $$$1$$$ to each edge. When we assign $$$1$$$ to the edge connecting $$$V_{R,i}$$$ and $$$V_{C,j}$$$, then $$$R_i$$$ and $$$C_j$$$ will toggle. We can consider $$$R_i$$$ and $$$C_j$$$ to be the weight of the vertices $$$V_{R,i}$$$ and $$$V_{C,j}$$$ respecitvely.
Consider a connected component of this bipartite graph. Choose an arbitrary spanning tree of this connected component. By assinging the weights of the edges in the spanning tree, we can arbitrarily set the weights of all but one vertex. We cannot arbitarily set the weight of all vertices as the xor-sum of the weight of vertices is an invariant.
Let us show that we can arbitarily choose the weights of all but one vertex on this connected component using the spanning tree. Let us arbitrarily root the tree. Choose some arbitrary leaf of the tree, if the weight of the leaf is correct, assign the edge connected to that vertex weight $$$0$$$. Otherwise, assign it weight $$$1$$$. Then remove the leaf and its corresponding edge. Actually, this shows that there is a one-to-one correspondents between the possible weights of the edges and the possible weights of the vertices.
For the edges not in the spanning tree we have chosen, we can arbitarily set their weights while we are still able to choose the weights of all but one vertex on this connected component by properly assigning weights of the edges in the spanning tree.
Suppose we want this constant value of $$$R$$$ and $$$C$$$ to be $$$v$$$, where $$$v$$$ is either $$$0$$$ or $$$1$$$.
Suppose that the connected component has size $$$n$$$, has $$$m$$$ edges and the xor of all the initial vertex weights is $$$x$$$.
If $$$n$$$ is even:
- If $$$x=0$$$, then there are $$$2^{m-n+1}$$$ ways to assign weights to edges.
- If $$$x=1$$$, then there are $$$0$$$ ways to assign weights to edges.
If $$$n$$$ is odd:
- If $$$x=v$$$, then there are $$$2^{m-n+1}$$$ ways to assign weights to edges.
- If $$$x\neq v$$$, then there are $$$0$$$ ways to assign weights to edges.