开关问题

AcWing-208-开关问题

分析

见《进阶指南》第163页。

实现

#include <iostream>
using namespace std;

const int N = 30;
int n, a[N], res;

bool Gauss () {
    for (int i = 1; i <= n; ++ i) {
        int idx = i;
        for (int j = i + 1; j <= n; ++ j)
            if (a[j] > a[idx])
                idx = j;
        swap(a[i], a[idx]);

        if (a[i] == 0) {
            res = 1 << (n - i + 1); // i - 1 个主元，n - i + 1 个自由元
            return true;
        }
        if (a[i] == 1) return false; // 0 = 1，无解

        for (int k = n; k >= 1; -- k) {
            if ((a[i] >> k) & 1) { // a[i][k] 为 1
                for (int j = 1; j <= n; ++ j)
                    if (j != i && ((a[j] >> k) & 1)) // a[j][k] 为 1
                        a[j] = a[j] ^ a[i];
                break; // 一次
            }
        }
    }
    return true;
}

int main () {
    int T;
    cin >> T;
    while (T --) {
        cin >> n;
        for (int i = 1; i <= n; ++ i) cin >> a[i];
        for (int i = 1, dst; i <= n; ++ i) {
            cin >> dst;
            a[i] = a[i] ^ dst;
        }
        for (int i = 1; i <= n; ++ i) // a[i][i] = 1
            a[i] = a[i] | (1 << i);
        int x, y;
        while (cin >> x >> y && x && y)
            a[y] = a[y] | (1 << x); // a[y][x] = 1
        
        res = 1;
        if (Gauss() == true) { // 有解
            cout << res << endl;
        } else {
            cout << "Oh,it's impossible~!!" << endl;
        }
    }
    return 0;
}