自动搬运

查看原文

来自洛谷，原作者为

	Brilliant11001 坦然迎接最后的结局 || AFO

搬运于2025-08-24 22:58:35，当前版本为作者最后更新于2024-09-11 20:18:48，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

更好的阅读体验

题目传送门

题目大意：

有 $n$ 个开关，$0$ 表示关，$1$ 表示开，每个开关还有带动的开关，若操作一个开关，那么它带动的开关也会相应变换。

现给出这 $n$ 个开关的初始状态 $s_i$ 和末状态 $t_i$，询问有多少种方法能将初始态转变为末态（不考虑操作先后顺序且每个开关至多操作一次）。

思路：

高斯消元解异或方程组经典题。

先考虑将原题抽象成方程组。

令 $x_i$ 表示第 $i$ 个开关的操作次数，因为每个开关至多操作一次，所以 $x_i = 0$ 或 $x_i = 1$。

令 $a_{i, j}$ 表示第 $i$ 个开关和第 $j$ 个开关之间的联系，若 $a_{i, j} = 1$，则表示操作 $j$ 会带动 $i$，若 $a_{i, j} = 0$ 表示无影响，特别的，因为操作自己就相当于带动自己，所以 $a_{i, i} = 1$。

再根据操作效果：$0$ 变 $1$，$1$ 变 $0$，和异或一模一样。

所以可以列出以下方程组：

$$\left\{\begin{matrix} a_{1, 1}x_1 \operatorname{xor} a_{1, 2}x_2 \operatorname{xor} \cdots \operatorname{xor} a_{1, n}x_n = t_1\operatorname{xor} s_1\\ a_{2, 1}x_1 \operatorname{xor} a_{2, 2}x_2 \operatorname{xor} \cdots \operatorname{xor} a_{2, n}x_n = t_2\operatorname{xor} s_2\\ \cdots\\ a_{n, 1}x_1 \operatorname{xor} a_{n, 2}x_2 \operatorname{xor} \cdots \operatorname{xor} a_{n, n}x_n = t_n\operatorname{xor} s_n \end{matrix}\right.$$

异或其实就是不进位加法，所以也可以用高斯消元来解，将加减法换为异或就行了。

这道题要求操作方案数，那么找自由元的数量就好了。因为若某个未知数是自由元，那么它取 $0$ 和 $1$ 都可以，于是贡献了两种方案，根据乘法原理，应该把自由元的数量这么多 $2$ 乘起来，即 $2^{cnt}$，$cnt$ 为自由元的数量。

同时由于系数只能为 $0$ 或 $1$，所以一个行向量可以压缩为一个二进制整数或者用 bitset 来操作，这样就能一次异或一整行，时间复杂度降低为 $O(\frac{n^3}{\omega})$，写起来也方便许多。

$\texttt{Code:}$

#include <cmath>
#include <bitset>
#include <iostream>

using namespace std;

const int N = 35;

int T;
int n;
bitset<N> a[N];
int ans;

int gauss() {
    int c, r;
    for(c = 0, r = 0; c < n; c++) {
        int t = r;
        for(int i = r + 1; i < n; i++)
            if(a[i][c]) {
                t = i;
                break;
            }
        
        if(!a[t][c]) continue;

        if(t != r) swap(a[t], a[r]);

        for(int i = r + 1; i < n; i++)
            if(a[i][c])
                a[i] = a[i] ^ a[r];
        ++r;
    }
    if(r < n) {
        for(int i = r; i < n; i++) {
            if(a[i][n])
                return -1;
        }
        ans = 1 << n - r;
        return 0;
    }
    return 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> T;
    while(T--) {
        cin >> n;
        ans = 1;
        int x;
        for(int i = 0; i < n; i++) 
            a[i].reset(), a[i].set(i, 1);
        for(int i = 0; i < n; i++) {
            cin >> x;
            a[i][n] = x;
        }
        for(int i = 0; i < n; i++) {
            cin >> x;
            a[i][n] = a[i][n] ^ x;
        }
        int y;
        while(cin >> x >> y && x && y)
            a[y - 1].set(x - 1, 1);
        int type = gauss();
        if(type >= 0) cout << ans << '\n';
        else cout << "Oh,it's impossible~!!" << '\n';
    }
    return 0;
}