关灯1【加强版】

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000;
int n, m;
int g[MAXN + 5][MAXN + 5];
int ans[MAXN + 5][MAXN + 5];
// p[pre] 上一行按键取决于哪些
// p[now] 当前行的按键~
// p[nxt] 下一行的按键~
// 1~m: x1~xm；m+1：是否要整体取反
int pre, now, nxt;
bitset<MAXN + 1 + 5> zeroB;
bitset<MAXN + 1 + 5> oneB; // 1~m+1 全都是 1
bitset<MAXN + 1 + 5> p[3][MAXN + 5];
// 滚动 pre,now,nxt
void freshNow()
{
    pre = now;
    now = nxt;
    nxt = 3 - pre - now;
}
void showFunc()
{
    cout << "---\n";
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= m + 1; j++)
            cout << p[now][i][j];
        cout << "\n";
    }
    cout << "---\n";
}
// 根据 ans[x] 和 ans[x-1] 算出来 g[x][y]
void freshG(int x, int y)
{
    g[x][y] ^= ans[x][y];
    if (y > 1)
        g[x][y] ^= ans[x][y - 1];
    if (y < m)
        g[x][y] ^= ans[x][y + 1];
    if (x > 1)
        g[x][y] ^= ans[x - 1][y];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> g[i][j];
    for (int i = 1; i <= m + 1; i++)
        oneB.set(i);
    // ---- 构造方程 ----
    // 第一行的案件情况
    pre = 0, now = 1, nxt = 2;
    for (int i = 1; i <= m; i++)
        p[now][i][i] = 1;
    // 循环生成下一行
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            p[nxt][j] = zeroB;      // 清空
            p[nxt][j] ^= p[now][j]; // 当前按键
            if (j > 1)
                p[nxt][j] ^= p[now][j - 1]; // 左边按键
            if (j < m)
                p[nxt][j] ^= p[now][j + 1]; // 右边按键
            p[nxt][j] ^= p[pre][j];         // 上面按键
            if (g[i][j] == 1)
                p[nxt][j][m + 1] = p[nxt][j][m + 1] ^ 1; // 是否要整体取反
        }
        freshNow();
    }
    // ---- 高斯消元 ----
    for (int i = 1; i <= m; i++)
    {
        for (int j = i; j <= m; j++)
            if (p[now][j][i] == 1)
            {
                swap(p[now][j], p[now][i]);
                break;
            }
        if (p[now][i][i] != 1)
            continue;
        // 消掉其他方程的第 i 列
        for (int j = 1; j <= m; j++)
            if (j != i && p[now][j][i] == 1)
                p[now][j] ^= p[now][i];
    }
    // ---- 生成解 ---
    // 第一行按键情况
    for (int i = 1; i <= m; i++)
        ans[1][i] = p[now][i][m + 1];
    // 依次推每一行
    for (int i = 2; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            freshG(i - 1, j);
            ans[i][j] = g[i - 1][j];
        }
    }
    int ansCnt = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            ansCnt += ans[i][j];
    cout << ansCnt;
    return 0;
}