高斯消元④-异或线性方程组,bitset优化-P3164

题目大意：

给你一个01矩阵大小 n ∗ m n*m n∗m.让你构造出一组非全零矩阵使得所有点它所相邻的数的1的个数为偶数.
n , m ≤ 40 n,m \leq 40 n,m≤40

题目思路:

跟POJ1830差不多，列 n ∗ m n*m n∗m个方程直接跑高斯消元即可.

复杂度: O ( ( n ∗ m ) 3 ) O((n*m)^3) O((n∗m)3)。可能会超时（实际上不会）。

加上bitset优化即可.复杂度为: O ( ( n ∗ m ) 3 64 ) O(\frac{(n*m)^3}{64}) O(64(n∗m)3​).–其实都不用改什么地方，把数组改成bitset,再把单个异或改成整行异或就好.实际快个400ms左右.

然后就是求具体解:先把*元答案全设为1.跑完高斯消元之后，对每一行选定第一个未知数求解它即可。

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 41;
bitset<maxn * maxn> a[maxn * maxn];
int nx[10] = {0,0,0,-1,1};
int ny[10] = {0,-1,1,0,0};
int res[maxn * maxn] , n , m;
void print ()
{
    cout << endl;
    for (int i = 1 ; i <= n * m ; i++){
        for (int j = 1 ; j <= n * m + 1; j++){
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1 ; i <= n ; i++)
        for (int j = 1 ; j <= m ; j++)
            for (int d = 0 ; d <= 4 ; d++){
                int t = (i - 1) * m + j;
                int gx = i + nx[d] , gy = j + ny[d];
                if (gx <= 0 || gx > n || gy <= 0 || gy > m) continue;
                int tt = (gx - 1) * m + gy;
                a[t][tt] = 1;
            }
    int way = n * m;
    // 高斯消元
    int r , c;
    for (r = c = 1 ; r <= way && c <= way ; r++ , c++){
        int p = 0;
        for (int j = r ; j <= way ; j++){
            if (a[j][c]) {
                p = j;
                break;
            }
        }
        if (!p){
            r--;
            res[c] = 1;
            continue;
        }
        swap(a[p] , a[r]);
        for (int j = 1 ; j <= way ; j++){
            if (j == r) continue;
            if (a[j][c] == 0) continue;
            a[j] ^= a[r];
        }
    }
    // 求一组特定解
    for (int i = 1 ; i <= way ; i++){
        int p = 0;
        // 求解这一行第一个1那个未知数
        for (int j = 1 ; j <= way ; j++){
            if (a[i][j]){
                p = j;
                break;
            }
        }
        if (!p) {
            continue;
        }
        //
        res[p] = a[i][way + 1];
        for (int j = p + 1 ; j <= way ; j++)
            res[p] ^= a[i][j];
    }
    for (int i = 1 ; i <= n ; i++){
        for (int j = 1 ; j <= m ; j++){
            cout << res[(i - 1) * m + j] << " ";
        }
        cout << endl;
    }
    return 0;
}