题目分析

需要构造一个 $m \times n$ 的 0-1 矩阵，满足每个位置及其上下左右邻居（如果存在）中 1 的个数为偶数。这包括位置本身和最多 4 个邻居。

解题思路

核心思想

将问题建模为模 2 线性方程组（GF(2)域）：

• 每个矩阵元素是一个变量（0 或 1）
• 每个位置对应一个方程，约束该位置及其邻居的异或和为 0
• 使用高斯消元法求解方程组

关键技术

• 线性方程组建模：将邻域约束转化为方程
• 高斯消元：在 GF(2) 域上求解
• bitset 优化：高效存储和操作大型稀疏矩阵

算法步骤

1. 建立线性方程组：每个位置对应一个方程
2. 高斯消元求解：在模 2 域上进行消元
3. 回代得到解：确定每个位置的值
4. 输出矩阵：按行列格式输出

完整代码

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// 读取输入
inline ll read() {
    ll x = 0, f = 1;
    char c = getchar();
    
    while (c < '0' || c > '9') {
        if (c == '-') f = 0;
        c = getchar();
    }
    
    while (c >= '0' && c <= '9') {
        x = (x << 3) + (x << 1) + (c ^ 48);
        c = getchar();
    }
    
    return f ? x : -x;
}

const int MAXN = 1605;  // 最大方程数 (40*40=1600)

int n, m;  // 矩阵的行数和列数
int ans[MAXN];  // 存储解
bitset<MAXN> equations[MAXN];  // 方程系数矩阵，使用bitset优化

// 方向数组：自身、右、左、下、上
int dx[5] = {0, 0, 0, 1, -1};
int dy[5] = {0, 1, -1, 0, 0};

// 将二维坐标转换为一维索引
inline int getIndex(int x, int y) {
    return (x - 1) * m + y;
}

// 高斯消元求解模2线性方程组
void gaussianElimination(int totalVars) {
    for (int i = 1; i <= totalVars; ++i) {
        // 寻找主元
        int pivot = i;
        while (pivot <= totalVars && !equations[pivot][i]) {
            pivot++;
        }
        
        if (pivot > totalVars) {
            // 自由变量，设为1保证非全零解
            equations[i][totalVars + 1] = 1;
            
            // 清除该行其他系数
            for (int j = i + 1; j <= totalVars; ++j) {
                equations[i][j] = 0;
            }
            
            // 更新后续方程
            for (int j = i + 1; j <= totalVars; ++j) {
                if (equations[j][i]) {
                    equations[j].flip(totalVars + 1);
                }
            }
            
            continue;
        }
        
        // 交换行
        if (i != pivot) {
            swap(equations[i], equations[pivot]);
        }
        
        // 消元
        for (int j = i + 1; j <= totalVars; ++j) {
            if (equations[j][i]) {
                equations[j] ^= equations[i];
            }
        }
    }
    
    // 回代求解
    for (int i = totalVars; i >= 1; --i) {
        ans[i] = equations[i][totalVars + 1];
        
        for (int j = i + 1; j <= totalVars; ++j) {
            if (equations[i][j]) {
                ans[i] ^= ans[j];
            }
        }
    }
}

int main() {
    // 读取矩阵尺寸
    n = read();
    m = read();
    
    int totalVars = n * m;  // 总变量数
    
    // 构建线性方程组
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int currentEq = getIndex(i, j);
            
            // 遍历当前位置及其邻居
            for (int k = 0; k < 5; ++k) {
                int ni = i + dx[k];  // 邻居行坐标
                int nj = j + dy[k];  // 邻居列坐标
                
                // 检查邻居是否在矩阵范围内
                if (ni >= 1 && ni <= n && nj >= 1 && nj <= m) {
                    int neighborVar = getIndex(ni, nj);
                    equations[currentEq][neighborVar] = 1;
                }
            }
        }
    }
    
    // 求解方程组
    gaussianElimination(totalVars);
    
    // 输出结果矩阵
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            int idx = getIndex(i, j);
            printf("%d", ans[idx]);
            if (j < m) printf(" ");
        }
        printf("\n");
    }
    
    return 0;
}

代码说明

关键数据结构

• equations[MAXN]：方程系数矩阵，使用 bitset 优化存储
• ans[MAXN]：存储每个变量的解（0 或 1）
• 方向数组：定义当前位置及其四个邻居的偏移量

算法核心

1. 问题建模

对于矩阵中的每个位置 $(i,j)$，建立方程：

a[i][j] ⊕ a[i-1][j] ⊕ a[i+1][j] ⊕ a[i][j-1] ⊕ a[i][j+1] = 0

其中 ⊕ 表示异或运算（模 2 加法）。

2. 高斯消元过程

消元阶段：

for (int j = i + 1; j <= totalVars; ++j) {
    if (equations[j][i]) {
        equations[j] ^= equations[i];
    }
}

在 GF(2) 域上，消元操作简化为异或运算。

自由变量处理：

if (pivot > totalVars) {
    equations[i][totalVars + 1] = 1;  // 设为1保证非全零解
    // ... 更新其他方程
}

当找不到主元时，该变量是自由变量，设为 1 以避免全零解。

3. 回代求解

for (int i = totalVars; i >= 1; --i) {
    ans[i] = equations[i][totalVars + 1];
    for (int j = i + 1; j <= totalVars; ++j) {
        if (equations[i][j]) {
            ans[i] ^= ans[j];
        }
    }
}

从最后一个方程开始，逐步求解每个变量。

数学原理

GF(2) 域性质：

• 加法：异或运算 (a ⊕ b)
• 乘法：与运算 (a & b)
• 每个元素的逆元是它自身

线性方程组：

• 系数矩阵是稀疏的（每个方程约 5 个非零元素）
• 使用 bitset 可以高效存储和操作

复杂度分析

• 空间复杂度：$O((mn)^2)$，但使用 bitset 大幅优化
• 时间复杂度：$O((mn)^3)$，但由于 bitset 的位运算优化和稀疏性，实际运行很快
• 可行性：$m,n \leq 40$，$mn \leq 1600$，在可接受范围内。