基础数学算法-开关问题

题目-开关问题

问题分析

$n$个开关相当于$n$个未知数, 假设对$1$号灯的初始状态是$0$, 目标状态是$1$, 假设有$x_2$和$x_3$开关会对其产生影响, 那么有方程$x_2\oplus x_3=1$

相当于是$n$个方程$n$个未知数, 高斯消元求解异或线性方程组, 基础数学算法中有对应的代码

但是该问题求的是方案数, 最终如果有解, 每一个自由变量只有两种选法
假设自由元的数量是$k$, 那么方案数等于$2^k$

算法步骤

• 构建线性异或方程组
• 高斯消元
• 计算自由元的个数, 假设是$0$, 实际只有一种方法
• 如果不是$1$, 最终结果就是$2^k$

代码实现

在多组测试用例的情况下, cin和printf不要混用!!!

#include <bits/stdc++.h>

using namespace std;

const int N = 35;

int T;
int n;
int f[N][N];

int gauss() {
   
    int r, c;
    for (r = c = 0; c < n; ++c) {
   
        int idx = r;

        for (int i = r + 1; i < n; ++i) {
   
            if (f[i][c]) {
   
                idx = i;
                break;
            }
        }

        if (!f[idx][c]) continue;

        for (int i = c; i <= n; ++i) swap(f[r][i], f[idx][i]);
        for (int i = r + 1; i < n; ++i) {
   
            for (int j = n; j >= c; --j) {
   
                f[i][j] ^= f[r][j] & f[i][c];
            }
        }
        r++;
    }

    if (r == n) return 1;
    int ans = 1;
    for (int i = r; i < n; ++i) {
   
        if (f[i][n]) return -1;
        ans *= 2;
    }

    return ans;
}

void solve() {
   
    memset(f, 0, sizeof f);
    cin >> n;
    for (int i = 0; i < n; ++i) cin >> f[i][n];
    for (int i = 0; i < n; ++i) {
   
        int val;
        cin >> val;
        f[i][n] ^= val;
    }

    for (int i = 0; i < n; ++i) f[i][i] = 1;
    int a, b;
    while (cin >> a >> b, a || b) f[b - 1][a - 1] = 1;

    int ans = gauss();
    if (ans == -1) cout << "Oh,it's impossible~!!" << '\n';
    else cout << ans << '\n';
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> T;
    while (T--) solve();

    return 0;
}