高斯消元求解异或方程


题意:给定一个五行六列的01矩阵,对于矩阵的每一个元素和其相邻的所有元素(因此一般为4个,边角部分为3或2个)可以选择是否进行一次操作:求元素值异或1。问哪些元素进行操作可以使所有的元素变为0.

思路:设元素(i,j)的值为v[i][j],并用f[i][j]表示f[i][j]和其相邻的元素是否求异或。那么有

\begin{equation}
v[i][j] \oplus f[i][j] \oplus f[i][j-1] \oplus f[i][j+1] \oplus f[i-1][j] \oplus f[i+1][j] = 0
\end{equation}

所以我们可以将矩阵里的每个点看作一个未知数,列出异或方程再求解(其实就是mod2意义下的同余方程)。由于异或有结合律、交换律,所以将两个方程异或的结果不会与原来的两个方程发生冲突。如{ $x+y+z=1$ } $\oplus$ { $x+z=0$ } $=$ { $y=1$ }

这样就可以用高斯消元法求解。由于每次列出的方程的系数部分完全相同,只是右边不同,且对于某个输入我们发现有唯一解,因此可以知道,在消元过程中绝对不会遇到无解的情况。