BZOJ 3503 和谐矩阵：异或高斯消元求任意非零解

题目大意

m×n 矩阵，每个格子填 0/1。要求每个格子与其上下左右四邻域的 1 的个数为偶数（含自身）。输出任意非全零解。

建模：GF(2) 线性方程组

• 变量 x_{i,j} ∈ {0,1} 共 m×n 个
• 每个格子一个方程：x_{i,j} ⊕ x_{i-1,j} ⊕ x_{i+1,j} ⊕ x_{i,j-1} ⊕ x_{i,j+1} = 0
• 共 m×n 个方程，异或即 GF(2) 加法

高斯消元（异或版）

1. 增广矩阵 A|b，此处 b 全 0（齐次方程组）
2. 列主元消元：寻找非零行交换、异或消去
3. 自由变元赋值：全零解不可接受，任置一自由变元 = 1
4. 回代得任意非零解

C++ 实现

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int MAX = 50;
const int dx[5] = {0,1,-1,0,0};
const int dy[5] = {0,0,0,1,-1};

int num[MAX][MAX];
int a[MAX*MAX][MAX*MAX];
bool ans[MAX*MAX];
int repr[MAX*MAX];

void gauss(int m, int n) {
    int cnt = m*n, now = 1;
    for (int col = 1; col <= cnt; ++col) {
        // 找主元行
        int pivot = now;
        for (int row = now+1; row <= cnt; ++row)
            if (a[row][col] > a[pivot][col]) pivot = row;
        if (pivot != now)
            for (int k = 1; k <= cnt; ++k) swap(a[now][k], a[pivot][k]);
        if (!a[now][col]) { // 自由变元
            ans[col] = 1; // 关键：置 1 得到非零解
            for (int row = 1; row <= cnt; ++row)
                if (a[row][col]) a[row][col] = 0, a[row][cnt+1] ^= 1;
            continue;
        }
        // 消去下方
        for (int row = now+1; row <= cnt; ++row)
            if (a[row][col])
                for (int k = col; k <= cnt; ++k)
                    a[row][k] ^= a[now][k];
        repr[now] = col;
        ++now;
    }
    // 回代
    for (int i = now-1; i >= 1; --i) {
        int col = repr[i];
        for (int j = 1; j < i; ++j)
            if (a[j][col]) a[j][col] = 0, a[j][cnt+1] ^= a[i][cnt+1];
        ans[col] = a[i][cnt+1];
    }
}

int main() {
    int m, n; cin >> m >> n;
    int cnt = 0;
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            num[i][j] = ++cnt;
    // 建方程
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            for (int k = 0; k < 5; ++k) {
                int x = i+dx[k], y = j+dy[k];
                if (x<1 || y<1 || x>m || y>n) continue;
                a[num[i][j]][num[x][y]] = 1;
            }
    gauss(m, n);
    for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j)
            printf("%d", ans[num[i][j]]);
        puts("");
    }
    return 0;
}

关键点

1. 齐次方程组必有解：全零解恒成立
2. 自由变元置 1：消元时遇到全零列，直接设该变元=1，同步更新常数项
3. SPJ 判题：任意合法非零解均可
4. 位运算加速：可用 bitset 或 unsigned long long 压位加速

复杂度

• 变量数 ≤ 2500，方程数 ≤ 2500
• 高斯消元 O(N³/64) 位压缩后极快