传送门

每个元素都有偶数个相邻的$1$，就是每个元素和相邻元素异或起来为$0$。

显然可以高斯消元。

把$(i,j)$元素的值设为$x_{i,j}$，就有方程：

$(x_{i,j})\ xor\ (x_{i-1,j})\ xor\ (x_{i+1,j})\ xor\ (x_{i,j-1})\ xor\ (x_{i,j+1})=0 $

当然这个方程组解集不是唯一的。题目中要求不允许答案全$0$矩阵，就把高斯消元中遇到的自由元的值定为$1$，再把剩余方程中含有该自由元的常数$xor$上$1$。异或方程组还可以用$bitset$优化。

时间复杂度：$O(n^3/32)$

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <bitset>

#define poi(x,y) ((x-1)*m+y)
//poi(x,y)将二维坐标转成一个整数

const int dx[5]={0,0,0,1,-1},dy[5]={0,1,-1,0,0};

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
template<typename T>
inline T read(){
    T x=0;
    int y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
int n,N,ans[1605];
//N是总元素个数(n*m)
bitset<1601>a[1605],rec[1605];
void Gauss(){
    for(register int i=1;i<=N;++i){
        int now=i;
        while(!a[now][i]&&now<N)++now;
        if(now!=i)swap(a[now],a[i]);
        if(!a[i][i]){
            //遇到自由元
            a[i][N+1]=1;
            for(register int j=i+1;j<=N;++j)
                a[i][j]=0;
            //常数赋值为1，系数赋值为0，也就是解为1
            for(register int j=i+1;j<=N;++j)
                if(a[j][i])a[j].flip(N+1);
            //该元素的解对其他方程的影响
            continue;
        }
        for(register int j=i+1;j<=N;++j)
            if(a[j][i])a[j]^=a[i];
    }
    for(register int i=N;i;--i){
        ans[i]=a[i][N+1];
        for(register int j=i+1;j<=N;++j)
            if(a[i][j])ans[i]^=ans[j];
    }
}
int main(){
    int n=read(),m=read();
    N=n*m;
    for(register int i=1;i<=n;++i){
        for(register int j=1;j<=m;++j){
            for(register int k=0;k<5;++k){
                int x=i+dx[k],y=j+dy[k];
                if(x<1||x>n||y<1||y>m)continue;
                a[poi(i,j)][poi(x,y)]=1;
            }
        }
    }
    Gauss();
    for(register int i=1;i<=n;++i,pn)
        for(register int j=1;j<=m;++j)
            printf("%d ",ans[poi(i,j)]);
}