高斯消元结束后，若存在系数为0，常数不为0的行，则方程无解
若系数不为0的行有k个，则说明主元有k个，自由元有n-k个，方程多解
/* 给定n个开关的初始状态si，要求将其变成目标状态di 规定： 每个开关最多进行一次操作 给定一组对应关系(i,j),如果操作第i个开关那么第j个开关也会受影响 请问有多少种操作方式 设xi=0|1表示没按/按了第i个开关 系数矩阵A[i][j]表示按第j个开关对第i个开关有影响，A[i][i]=1 那么可以得到方程组 A[i][1]*x1 ^ A[i][2]*x2 ^ ... ^ A[i][n]*xn = si^di 把常数左移可得 A[i][1]*x1 ^ A[i][2]*x2 ^ ... ^ A[i][n]*xn ^ si^di = 0 方程组中的 A[i][j]*xj 代表第j个开关对第i个开关产生的影响，显然只有两个都为1时才会有影响 那么对以上方程组使用高斯消元即可！ 可以对A数组进行状态压缩，A[i]表示第i个方程的系数矩阵，共n+1位，其中1-n表示系数，n+1表示常数 由于x的取值只能是0或1 所以有i个自由原，操作方式就有1<<i种 */ #include<iostream> #include<cstring> #include<cstdio> using namespace std; int A[100],n,t,ans; int main(){ cin>>t; while(t--){ cin>>n; //处理第n+1位，即常数 for(int i=1;i<=n;i++)cin>>A[i]; for(int i=1;i<=n;i++){ int tmp=0; cin>>tmp; A[i]^=tmp; } for(int i=1;i<=n;i++) A[i]|=1<<i;//处理A[i][i] int i,j; while(cin>>i>>j && i)//A[j][i]=1 A[j]|=1<<i; ans=1; //开始高斯消元！ for(int i=1;i<=n;i++){ //找到最大的A[i],即主元位最高的a[i] for(int j=i;j<=n;j++) if(A[j]>A[i])swap(A[j],A[i]); //只有i-1个主元 if(A[i]==0){ans=1<<(n-i+1);break;} //只有常数项不是0 if(A[i]==1){ans=0;break;} //把其余方程的A[i]的最高位减去 for(int k=n;k;k--) if(A[i]>>k & 1){//找到A[i]最高位的主元 for(int j=1;j<=n;j++) if(j!=i && (A[j]>>k & 1))A[j]^=A[i]; break; } } if(ans==0) puts("Oh,it's impossible~!!"); else cout<<ans<<endl; } }