|
|
|
|
|
#include <bits/stdc++.h>
|
|
|
|
|
|
using namespace std;
|
|
|
|
|
|
const int N = 110;
|
|
|
|
|
|
int n;
|
|
|
|
|
|
int a[N][N];
|
|
|
|
|
|
|
|
|
|
|
|
int gauss() {
|
|
|
|
|
|
int r = 1;
|
|
|
|
|
|
for (int c = 1; c <= n; c++) {
|
|
|
|
|
|
int t = r;
|
|
|
|
|
|
for (int i = r + 1; i <= n; i++)
|
|
|
|
|
|
if (a[i][c]) t = i;
|
|
|
|
|
|
if (!a[t][c]) continue;
|
|
|
|
|
|
swap(a[t], a[r]);
|
|
|
|
|
|
for (int i = r + 1; i <= n; i++)
|
|
|
|
|
|
for (int j = n + 1; j >= c; j--)
|
|
|
|
|
|
if (a[i][c]) a[i][j] ^= a[r][j];
|
|
|
|
|
|
r++;
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
int res = 1;
|
|
|
|
|
|
// 此时已经到了全零行
|
|
|
|
|
|
if (r < n + 1) {
|
|
|
|
|
|
for (int i = r; i <= n; i++) {
|
|
|
|
|
|
// 全零行的右边出现非零 无解
|
|
|
|
|
|
if (a[i][n + 1]) return -1; // 出现了 0 == !0，无解
|
|
|
|
|
|
// 如果出现了0=0这样的情况，可能是 0x1+0x2+0x3 这样的情况，
|
|
|
|
|
|
// 此时，不管x1,x3取什么值(0,1),都与结果无关，所以自由元数量的2次方就是答案
|
|
|
|
|
|
// 比如x1=0,x1=1-->2个答案
|
|
|
|
|
|
// 比如x2=0,x2=1-->2个答案
|
|
|
|
|
|
// 比如x3=0,x3=1....
|
|
|
|
|
|
// 同时这些 x1,x2,x3的取值是可以随意取的，每个有2种取法，是一个典型的乘法原理，即2*2*2*...，数量就是自由元的数量
|
|
|
|
|
|
// 现在就是循环中，所以，可以利用循环，每次乘2就完成了2次方的计算
|
|
|
|
|
|
res <<= 1;
|
|
|
|
|
|
}
|
|
|
|
|
|
}
|
|
|
|
|
|
return res;
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
int main() {
|
|
|
|
|
|
int T;
|
|
|
|
|
|
cin >> T; // T组测试数据
|
|
|
|
|
|
while (T--) {
|
|
|
|
|
|
memset(a, 0, sizeof a); // 多组测试数据，不清空OI一场空
|
|
|
|
|
|
cin >> n; // 开关个数
|
|
|
|
|
|
for (int i = 1; i <= n; i++) cin >> a[i][n + 1]; // 初始状态
|
|
|
|
|
|
for (int i = 1; i <= n; i++) { // 终止状态
|
|
|
|
|
|
int t; // 第i个开关的终止状态
|
|
|
|
|
|
cin >> t;
|
|
|
|
|
|
// s1: 1号开关的初始状态 t1:1号开关的结束状态
|
|
|
|
|
|
// x1 x2 x3 ... xn 1~n个开关是否按下，0：不按下，1：按下
|
|
|
|
|
|
// a13:3号开关影响1号开关状态， a1n:n号开关影响1号开关状态.
|
|
|
|
|
|
// 推导的方程
|
|
|
|
|
|
// 含义：从初始状态 s1开始出发，最终到达t1这个状态。
|
|
|
|
|
|
// 有些开关是可以影响1号开关的最终状态，有些变化了也不影响。我们把开关之间的关联关系设为a_ij,描述j开关变化，可以影响到i开关
|
|
|
|
|
|
// 如果 a_ij=0，表示j开关不会影响i开关，不管x_j=1，还是x_j=0都无法影响i开关的状态。
|
|
|
|
|
|
|
|
|
|
|
|
// s1^ a11*x1 ^ a12*x2 ^ a13*x3 ^ ... ^a1n*xn=t1
|
|
|
|
|
|
// <=>
|
|
|
|
|
|
// s1^ s1 ^ a11*x1 ^ a12*x2 ^ a13*x3 ^ ... ^a1n*xn= t1 ^ s1
|
|
|
|
|
|
// <=>
|
|
|
|
|
|
// a11*x1 ^ a12*x2 ^ a13*x3 ^ ... ^a1n*xn= t1 ^ s1
|
|
|
|
|
|
|
|
|
|
|
|
// 这里初始化时 a[1][n+1]就是s1,下面这行的意思就是 t1 ^ s1
|
|
|
|
|
|
a[i][n + 1] ^= t; // 在维护增广矩阵的最后一列数值
|
|
|
|
|
|
a[i][i] = 1; // 第i个开关一定会改变第i个灯,形成一个三角？
|
|
|
|
|
|
}
|
|
|
|
|
|
|
|
|
|
|
|
int x, y;
|
|
|
|
|
|
while (cin >> x >> y, x && y) a[y][x] = 1; // 操作开关x,x影响y。生成左侧方程系数。给定的是1，未说明的是0
|
|
|
|
|
|
// 这个矩阵系数，第一维的是行，第二维的是列
|
|
|
|
|
|
// 上面的输入，其实是反的，比如它说，3影响1，其实真正的含义是a_13=1
|
|
|
|
|
|
|
|
|
|
|
|
// 系数矩阵准备完毕，可以用高斯消元求解方程了
|
|
|
|
|
|
int t = gauss();
|
|
|
|
|
|
if (t == -1)
|
|
|
|
|
|
puts("Oh,it's impossible~!!");
|
|
|
|
|
|
else
|
|
|
|
|
|
printf("%d\n", t);
|
|
|
|
|
|
}
|
|
|
|
|
|
return 0;
|
|
|
|
|
|
}
|
