自动搬运

查看原文

来自洛谷，原作者为

	stoorz **

搬运于2025-08-24 21:45:58，当前版本为作者最后更新于2020-02-28 18:16:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

对于矩阵中的一个点 $(x,y)$，就是要我们求出一种方案满足 $a[x][y]\ \operatorname{xor}\ a[x-1][y]\ \operatorname{xor}\ a[x+1][y]\ \operatorname{xor}\ a[x][y-1]\ \operatorname{xor}\ a[x][y+1]=0$。

那么我们对于每一个点 $(x,y)$，我们可以列出一个形如 $a_1x_1\ \operatorname{xor}\ a_2x_2\ \operatorname{xor}\ ...\ \operatorname{xor}\ a_{nm}x_{nm}=0$ 的方程。其中如果一个点与 $(x,y)$ 相邻或就是 $(x,y)$，那么该位置的系数 $a=1$，否则 $a=0$。

然后就是高斯消元板子了。

时间复杂度 $O$ $\Large{(}$ $(nm)^3$ $\Large{)}$。显然跑不过。 我们发现，题目要求是 01 矩阵，每一位的取值就只有 0 或 1。所以可以用 $\operatorname{bitset}$ 搞搞，可以简单理解为状压。时间复杂度 $O(\frac{(nm)^3}{32})$。

#include <cstdio>
#include <bitset>
#include <cstring>
#include <algorithm>
using namespace std;

const int N=50;
const int dx[]={0,0,0,-1,1},dy[]={0,-1,1,0,0};
int n,m,id[N][N],ans[N*N];
bitset<N*N> a[N*N];

void gauss()
{
	for (int i=1;i<=n*m;i++)
	{
		for (int j=i;j<=n*m;j++)
			if (a[j][i]>0)  //找到一个该位置系数为 1 的方程
			{
				swap(a[i],a[j]);
				break;
			}
		if (!a[i][i]) ans[i]=1;  //这项是自由元，直接取 1 即可
		for (int j=i+1;j<=n*m;j++)
			if (a[j][i]) a[j]^=a[i];
	}
	for (int i=n*m;i>=1;i--)
		for (int j=i+1;j<=n*m;j++)
			ans[i]^=(ans[j]*a[i][j]);  //求解
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			id[i][j]=(i-1)*m+j;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
		{
			for (int k=0;k<=4;k++)
			{
				int x=i+dx[k],y=j+dy[k];
				if (x<1 || y<1 || x>n || y>m) continue;
				a[id[i][j]][id[x][y]]=1;
			}
		}
	gauss();
	for (int i=1;i<=n*m;i++)
	{
		printf("%d ",ans[i]);
		if (i%m==0) putchar(10);
	}
	return 0;
}