Luogu

BZOJ

分析

对每个位置设一个未知数,然后可以列出 $n\times m$ 个异或方程。

因为不能全为 $0$ ,所以考虑再加一个方程,强制 $(1,1)$ 选 $1$ 。

这样子是 $O(n^3m^3)$ 的,但是因为是异或方程,所以可以拿 $\mathrm{bitset}$ 优化一下。

然后,就变成了 $O(\frac{n^3m^3}{64})$ ,再加上高斯消元的小常数,完全能过。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <bitset>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=40+10;

int n,m;
int id[N][N],tot=0;
bitset<1603> a[1603];
int b[1603];

inline void Gauss() {
    for (re int i=1;i<=n*m;++i) {
        int pos=i;
        while (pos<=n*m+1&&!a[pos][i]) ++pos;
        if (pos!=i) swap(a[pos],a[i]),swap(b[pos],b[i]);
        for (re int j=1;j<=n*m+1;++j) {
            if (i==j) continue;
            if (a[j][i]) a[j]^=a[i],b[j]^=b[i];
        }
    }
}

int main() {
    n=read(),m=read();
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=m;++j)
            id[i][j]=++tot;
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=m;++j) {
            a[id[i][j]][id[i][j]]=1;
            if (i>1) a[id[i][j]][id[i-1][j]]=1;
            if (j>1) a[id[i][j]][id[i][j-1]]=1;
            if (i<n) a[id[i][j]][id[i+1][j]]=1;
            if (j<m) a[id[i][j]][id[i][j+1]]=1;
        }
    a[n*m+1][1]=1,b[n*m+1]=1;

    Gauss();

    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=m;++j)
            printf("%d%c",b[id[i][j]]," \n"[j==m]);
    return 0;
}
最后修改:2019 年 09 月 25 日 01 : 29 PM