「poj 1830」开关问题 (高斯消元解线性 Xor 方程)

poj 1830
题意：见上。
设$x_i$为$i$开关是否(0/1)操作，$a_{i,j}$为$j$开关操作后是否(1/0)会影响$i$开关

则可以列出线性异或方程组

$$
\begin{cases}
a_{1,1}x_1 xor a_{1,2}x_2 xor … xor a_{1,n}x_n = st_1 xor ed_1 \\
a_{2,1}x_1 xor a_{2,2}x_2 xor … xor a_{2,n}x_n = st_2 xor ed_2 \\
\vdots \\
a_{n,1}x_1 xor a_{n,2}x_2 xor … xor a_{n,n}x_n = st_n xor ed_n
\end{cases}
$$

高斯消元即可。

知识点：
1、自由元最后统计

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<bitset>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

namespace flyinthesky { 

    const int MAXN = 35;

    int n, a[MAXN];
    bitset<MAXN> bs[MAXN];

    int ksm(int a, int b) {
        int bs = a, ans = 1;
        while (b) {
            if (b & 1) ans *= bs;
            bs *= bs;
            b >>= 1;
        }
        return ans;
    }

    void clean() {
    }
    int solve() {
        clean();
        cin >> n;
        for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
        for (int x, i = 1; i <= n; ++i) scanf("%d", &x), a[i] ^= x;
        for (int i = 1; i <= n; ++i) bs[i].reset(), bs[i][0] = a[i], bs[i][i] = 1;
        int x, y;
        while (scanf("%d%d", &x, &y) == 2 && x && y) bs[y][x] = 1;
        int ans = 1, whw = 0;
        for (int i = 1; i <= n; ++i) { // 每列
             if (bs[i][i] == 0) {
                 for (int j = i + 1; j <= n; ++j) if (bs[j][i]) {swap(bs[j], bs[i]); break;}
             }
             if (bs[i][0] == 1 && bs[i].count() == 1) {ans = 0; break ;}
             if (bs[i][i] == 0) ++whw;
             for (int j = i + 1; j <= n; ++j) if (bs[j][i]) bs[j] ^= bs[i];
        }
        if (ans == 0) printf("Oh,it's impossible~!!\n"); else printf("%d\n", ksm(2, whw));
        return 0; 
    }
}
int main() {
    int k; cin >> k;
    while (k--) flyinthesky::solve();
    return 0;
}