Description：

构造一个 $01$ 矩阵使得任何一个元素他和他周围五个元素有偶数个 $1$ 。

$1\le n \le 40$

Solution：

高斯消元解异或方程组，对于方程组中的所有系数，只有 $0$ 和 $1$ ，分别代表这个未知数对这个方程有无影响，但是感觉影响会有正有负，其实是没有区别的，只要调整一下方程右边的结果即可。

对于这题，发现如果第一行的结果确定了（第零行其实已经确定了，都是零），那么整个矩阵的状态就已经确定了，可以递推一下每个数受第一行那些数字影响，而存在一个矩阵合法当且仅当第 $m+1$ 行全为零，这样我们就有了 $m$ 个方程，方程右边都是零，用高斯消元解一遍方程，在回代的时候，把所有自由元的取值都设成一，因为不允许全零矩阵，主元直接解出即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 43

typedef long long ll;

ll f[MAXN][MAXN];

ll a[MAXN];

ll res[MAXN][MAXN];

ll c[MAXN][MAXN];

void gauss(int k)

{

	for(int i = 1;i <= k;++i)

	{

		if(!(a[i] & (1ll << i)))

			for(int j = i + 1;j <= k && !(a[i] & (1ll << i));++j)

				if(a[j] & (1ll << i))

					swap(a[i],a[j]);

		if((a[i] & (1ll << i)) == 0)continue;

		for(int j = i + 1;j <= k;++j)

			if(a[j] & (1ll << i))

				a[j] ^= a[i];

	}

	for(int i = k;i >= 1;--i)

	{

		if(a[i] & (1ll << i))c[1][i] = ((a[i] >> (m + 1)) & 1);

		else c[1][i] = 1;

		for(int j = i - 1;j >= 1;--j)

			if(a[j] & (1ll << i))a[j] ^= (c[1][i] << (m + 1));

	}

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= m;++i)

		f[1][i] |= (1ll << i);

	for(int i = 2;i <= n + 1;++i)

		for(int j = 1;j <= m;++j)

			f[i][j] = f[i - 1][j] ^ f[i - 1][j - 1] ^ f[i - 1][j + 1] ^ f[i - 2][j];

	for(int i = 1;i <= m;++i)a[i] = f[n + 1][i];

	gauss(m);

	for(int i = 2;i <= n;++i)

		for(int j = 1;j <= m;++j)

			c[i][j] = c[i - 1][j] ^ c[i - 1][j - 1] ^ c[i - 1][j + 1] ^ c[i - 2][j];

	for(int i = 1;i <= n;++i)

	{

		for(int j = 1;j <= m;++j)

		{

			putchar('0' + c[i][j]);

			putchar(' ');

		}

		puts("");

	}

	return 0;

}