题意：给出$N,M$，试构造一个$N \times M$的非全$0$矩阵，其中所有格子都满足：它和它上下左右四个格子的权值之和为偶数。$N , M \leq 40$
可以依据题目中的条件列出有$N \times M$的元、$N \times M$个方程的异或方程组（异或方程组就是所有位置都是$1$或$0$，最右边一列的答案需要通过异或互相消除的方程组，一般在$mod\,2$意义下产生）。
理论上元和方程组数量一致的时候每一个元都是有唯一解的，但是在有解的情况下，其中一些方程是线性相关的，这意味着消到最后，某一些行会变成全$0$（如果不是很清楚可以像$vegetable chicken$我一样打一波$3 \times 3$和$4 \times 4$的表）。我们可以把行全$0$的元（又称之为自由元）全部设为$1$，因为它们是多少对方程最后有无解没有关系，然后一步步把上面推出来即可。
因为复杂度为$1600^3$平常的高斯消元速度很慢，所以可以用神仙$STL\,bitset$优化
1 #include2 using namespace std; 3 4 inline int read(){ 5 int a = 0; 6 bool f = 0; 7 char c = getchar(); 8 while(c != EOF && !isdigit(c)){ 9 if(c == '-')10 f = 1;11 c = getchar();12 }13 while(c != EOF && isdigit(c)){14 a = (a << 3) + (a << 1) + (c ^ '0');15 c = getchar();16 }17 return f ? -a : a;18 }19 20 const int dir[5][2] = { 0,1,0,-1,1,0,-1,0,0,0};21 bitset < 1600 > gauss[1600] , ans;22 23 int main(){24 #ifdef LG25 freopen("3164.in" , "r" , stdin);26 freopen("3164.out" , "w" , stdout);27 #endif28 int M , N;29 cin >> M >> N;30 for(int i = 0 ; i < M ; i++)31 for(int j = 0 ; j < N ; j++)32 for(int k = 0 ; k < 5 ; k++)33 if(i + dir[k][0] >= 0 && i + dir[k][0] < M && j + dir[k][1] >= 0 && j + dir[k][1] < N)34 gauss[i * N + j][(i + dir[k][0]) * N + j + dir[k][1]] = 1;35 int now = 0;36 for(int i = 0 ; i < M * N ; i++){37 int j = now;38 while(j < M * N && !gauss[j][i])39 j++;40 if(j == M * N)41 continue;42 if(j != now)43 swap(gauss[now] , gauss[j]);44 while(++j < M * N)45 if(gauss[j][i])46 gauss[j] ^= gauss[now];47 now++;48 }49 for(int i = M * N - 1 ; i >= 0 ; i--){50 if(!gauss[i][i])51 ans[i] = 1;52 if(ans[i])53 for(int j = i - 1 ; j >= 0 ; j--)54 if(gauss[j][i])55 ans[j] = ans[j] ^ 1;56 }57 for(int i = 0 ; i < M ; i++){58 for(int j = 0 ; j < N ; j++){59 putchar(ans[i * N + j] + 48);60 putchar(' ');61 }62 putchar('\n');63 }64 return 0;65 }