题意：给你N个开关，其中某些开关之间是相互影响的，即一个开关控制多个，那么每个开关操作与否为一个变元，有N个变元，开关之间相互影响的系数设为1，否则为0，对模2高斯消元求解自由变元个数。
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; const int maxn=30; int n,m;//有n个方程,m个未知数 int a[maxn][maxn]; int x[maxn];//解集 bool free_x[maxn];//判断是否为自由变元 int free_num;//记录自由变元的个数 int gcd(int a,int b) { return b==0?a:gcd(b,a%b); } int lcm(int a,int b) { return a*b/gcd(a,b); } //返回-2表示有浮点数解，但无整数解；返回-1表示无解；返回fjfj0表示有唯一解；返回1表示有无穷个解 int gauss() { int i,j,k; int max_r;//当前这列绝对值最大的行 int col;//当前处理的列 int ta,tb; int LCM; int temp; int free_x_num; int free_index; col=0; for(k=0;k<n&&col<m;k++,col++) {//枚举当前处理的行 max_r=k; for(i=k+1;i<n;i++) { if(abs(a[i][col])>abs(a[max_r][col])) max_r=i; } if(max_r!=k) {//与第k行交换 for(j=k;j<m+1;j++) swap(a[k][j],a[max_r][j]); } if(a[k][col]==0) {//说明该col列第k行以下全都是0了，则处理当前行的下一列 k--; continue; } for(i=k+1;i<n;i++) {//枚举要删去的行 if(a[i][col]!=0) { LCM=lcm(abs(a[i][col]),abs(a[k][col])); ta=LCM/abs(a[i][col]),tb=LCM/abs(a[k][col]); if(a[i][col]*a[k][col]<0) ta=-tb;//异号的情况是两个数相加 for(j=col;j<m+1;j++) { a[i][j]=((a[i][j]*ta)%2-(a[k][j]*tb)%2+2)%2; } } } } for(i=k;i<n;i++) { if(a[i][col]!=0) return -1; } if(k<m) { for(i=k-1;i>=0;i--) { free_x_num=0; for(j=0;j<m;j++) { if(a[i][j]!=0&&free_x[j]) free_x_num++,free_index=j; } if(free_x_num>1) continue; temp=a[i][m]; for(j=0;j<m;j++) { if(a[i][j]!=0&&j!=free_index) temp-=a[i][j]*x[j]; } x[free_index]=temp/a[i][free_index]; free_x[free_index]=0; } return m-k;//自由变元有m-k个 } for(i=m-1;i>=0;i--) { temp=a[i][m]; for(j=i+1;j<m;j++) { if(a[i][j]!=0) temp-=a[i][j]*x[j]; } if(temp%a[i][i]!=0) return -2; x[i]=temp/a[i][i]; } return 0; } int c[maxn],t[maxn]; int main() { int k,x,y; scanf("%d",&k); while(k--) { memset(a,0,sizeof a); memset(free_x,1,sizeof free_x); scanf("%d",&m); n=m; for(int i=0;i<m;i++) a[i][i]=1; for(int i=0;i<m;i++) scanf("%d",&c[i]); for(int i=0;i<m;i++) scanf("%d",&t[i]); while(scanf("%d%d",&x,&y)) { if(x==0&&y==0) break; a[y-1][x-1]=1; } for(int i=0;i<n;i++) { a[i][m]=(t[i]-c[i]+2)%2; } free_num=gauss(); //cout<<"自由变元个数:"<<free_num<<endl; if(free_num==-1||free_num==-2) puts("Oh,it's impossible~!!"); else printf("%d\n",(1<<free_num)); } return 0; }
