View Code
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath> 5 #include<algorithm> 6 using namespace std; 7 8 const int maxn= 110; 9 int a[maxn][maxn]; 10 int n,a1[maxn],a2[maxn]; 11 inline int fab( int x) 12 { 13 return x> 0?x:-x; 14 } 15 inline void swap( int &x, int &y) 16 { 17 int temp=x; 18 x=y; 19 y=temp; 20 } 21 int Gauss() 22 { 23 int i,j,k,max_r,t; 24 for(i= 0,j= 0;i<n&&j<n;i++,j++) 25 { 26 max_r=i; 27 for(k=i+ 1;k<n;k++) 28 if(fab(a[k][j])>fab(a[max_r][j])) 29 max_r=k; 30 if(max_r!=i) 31 { 32 for(t=j;t<=n;t++) 33 swap(a[i][t],a[max_r][t]); 34 } 35 if(a[i][j]== 0) 36 { 37 i--; 38 continue; 39 } 40 for(k=i+ 1;k<n;k++) 41 { /* 42 if(a[k][j]!=0) 43 { 44 for(t=j;t<n+1;t++) 45 a[k][t]=a[k][t]^a[i][t]; 46 } */ 47 if(a[k][j]== 0) 48 continue; 49 for(t=j;t<=n;t++) 50 a[k][t]=a[k][t]^a[i][t]; 51 } 52 } 53 for(k=i;k<n;k++) // 无解 54 if(a[k][n]!= 0) 55 return - 1; 56 if(i==n) // 唯一解 57 return 1; 58 return 1<<(n-i); // 有n-i个未知变量 59 } 60 int main() 61 { 62 int k,i; // int k,n,i; 63 scanf( " %d ",&k); 64 while(k--) 65 { 66 scanf( " %d ",&n); 67 memset(a, 0, sizeof(a)); 68 for(i= 0;i<n;i++) 69 scanf( " %d ",&a1[i]); 70 for(i= 0;i<n;i++) 71 scanf( " %d ",&a2[i]); 72 int y,z; 73 while(scanf( " %d %d ",&y,&z)&&y!= 0&&z!= 0) 74 { 75 a[y- 1][z- 1]= 1; 76 } 77 for(i= 0;i<n;i++) 78 { 79 a[i][i]= 1; 80 a[i][n]=a1[i]^a2[i]; // why??? 81 /* if(a1[i]!=a2[i]) 82 a[i][n]=1; 83 else 84 a[i][n]=0; */ 85 } 86 int ans=Gauss(); 87 if(ans==- 1) 88 printf( " Oh,it's impossible~!!\n "); 89 else 90 printf( " %d\n ",ans); 91 } 92 return 0; 93 94