高斯消元求解异或方程

题意：给定一个五行六列的 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$ }

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

#include <iostream>
#include <cstdio>
#include <cstring>

#define MX 50

using namespace std;

int mat[MX][MX],ans[MX];
const int n=30;

void init()
{
    memset(mat,0,sizeof(mat));
    for(int i=1;i<=5;i++)
    {
        for(int j=1;j<=6;j++)
        {
            if(i>=2)mat[(i-1)*6+j][(i-2)*6+j]=1;
            if(i<=4)mat[(i-1)*6+j][(i)*6+j]=1;
            if(j>=2)mat[(i-1)*6+j][(i-1)*6+j-1]=1;
            if(j<=5)mat[(i-1)*6+j][(i-1)*6+j+1]=1;
            mat[(i-1)*6+j][(i-1)*6+j]=1;
        }
    }
}

void input()
{
    for(int i=1,a=0;i<=n;i++)scanf("%d",&a),mat[i][0]=a;
}

void gauss()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)if(mat[j][i]==1){swap(mat[j],mat[i]);break;}
        for(int j=i+1;j<=n;j++)if(mat[j][i])for(int k=0;k<=n;k++)mat[j][k]^=mat[i][k];
    }
    for(int i=n;i>=1;i--)
    {
        ans[i]=mat[i][0];
        for(int j=n;j>i;j--)ans[i]^=(mat[i][j]&ans[j]);
    }
}

int main()
{
    int t;
    scanf("%d",&t);
    for(int w=1;w<=t;w++)
    {
        init();
        input();
        gauss();
        cout<<"PUZZLE #"<<w<<endl;
        for(int i=1;i<=n;i++)
        {
            cout<<ans[i]<<" ";
            if(i%6==0)cout<<endl;
        }
    }
    return 0;
}