高斯消元求解异或方程


题意:给定一个五行六列的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;
}
分类: 文章

3 条评论

彭书博 · 2017年6月24日 8:11 上午

%%%%%%%
%%dalao%%

litble · 2017年5月30日 9:32 下午

$orz^{orz^{orz^{orz^{orz}}}}$
dalao太强了

konnyakuxzy · 2017年5月30日 7:15 下午

%%%%%%%
本蒟蒻完全不会啊Orz
abs大佬太强啦Orz

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *