题目链接
将题目转化为矩乘问题
构建一个 \(n \times n\) 的开关信息矩阵，其中第 \(i\) 列第 \(j\) 行的元素为 \(0 / 1\) 代表在改变开关 \(i\) 的情况下开关 \(j\) 是否会改变
将该开关信息矩阵乘上一个 \(n\times 1\) 的答案矩阵，其中第 \(i\) 行的元素为 \(0/1\) 代表是否拉第 \(i\) 个开关
得到的是一个 \(n\times 1\) 的矩阵，将其与开关的初始状态矩阵 逐位相异或(注意，不是矩乘) 若得到开关的结果状态矩阵，则答案加一
利用异或的性质 a^b=b^a ，将结果矩阵逐位异或上初始矩阵，我们就得到了矩乘的标准形式 \(Ax=b\)
最后的答案即为 \(x\) 的 \(2\) 的自由元个数次方 (因为每个自由元只可取 \(0/1\))，也即 \(2\) 的 \(n-rank(A)\) 次方
下面是代码：
#include <iostream>
#include <cstring>
using namespace std;
const int MAX_N = 50;
int mat[MAX_N][MAX_N];
int Gauss(int n) {
int rank = 0;
for (int col = 0; col < n; ++col) { // 逐列找 pivot
int pivotRow = -1;
for (int row = rank; row < n; ++row) {
if (mat[row][col]) { // 找到了，记录 pivot 所在行的位置
pivotRow = row;
break;
}
}
if (pivotRow == -1) continue; // 没找到，自由元++
for (int i = 0; i <= n; ++i)
swap(mat[pivotRow][i], mat[rank][i]); // 将 pivot 所在行的位置交换到第 rank 行(行数从 0 开始) 以形成下三角矩阵
for (int i = rank + 1; i < n; ++i) {
if (mat[i][col]) {
for (int j = col; j <= n; ++j) mat[i][j] ^= mat[rank][j]; // 异或消元
}
}
++rank; // 矩阵的阶++
}
for (int row = rank; row < n; ++row)
if (mat[row][n]) return -1; // 高消后此时 rank+1 ~ n 行左边全为 0，若最右元素仍不为 0 则出现了 0=n，方程无解
return rank; // 返回矩阵 A 的阶
}
int main() {
int k;
cin >> k;
while (k--) {
int n;
cin >> n;
for (int i = 0; i < n; ++i)
mat[i][i] = 1;
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
mat[i][n] ^= x;
}
for (int i = 0; i < n; ++i) {
int x;
cin >> x;
mat[i][n] ^= x; // 构建 b 结果状态矩阵(向量)
}
int x, y;
while (cin >> x >> y) {
if (!x && !y) break;
mat[y - 1][x - 1] = 1; // 构建 A 矩阵
}
int ans = Gauss(n);
if (~ans) {
cout << (1 << (n - ans)) << endl; // n-rank(A) 即自由元个数，每个自由元都有 0/1 两种可能取值
} else {
cout << "Oh,it's impossible~!!" << endl;
}
memset(mat, 0, sizeof(mat));
}
return 0;
}
