更好的阅读体验
题目传送门
题目大意：
有 \(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;
}