题意：
有N个相同的开关，每个开关都与某些开关有着联系，每当你打开或者关闭某个开关的时候，其他的与此开关相关联的开关也会相应地发生变化，即这些相联系的开 关的状态如果原来为开就变为关，如果为关就变为开。你的目标是经过若干次开关操作后使得最后N个开关达到一个特定的状态。对于任意一个开关，最多只能进行 一次开关操作。你的任务是，计算有多少种可以达到指定状态的方法。（不计开关操作的顺序）
题解：这题是给定N个灯的初始和最终状态，再给定一些关系，这些关系说明按某个开关可能影响其他的灯的开关情况，可以将这种关系视为一种取反的关系。
对于这题我们假设一组数据：
3
0 1 0
1 1 0
1 2
2 3
1 3
3 2
0 0
对于以上的数据，我们用矩阵来表示整个操作的过程和状态
0 1
S = 1 E = 1
0 0
我们可以很显然的知道，某个等的亮灭情况将体现出各个开关的复合结果，因此我们可以得到这样的方程组，模二加等价于异或操作：
E(a) = xa*A11 ^ xb*A12 ^ xc*A13 ^ S(a);
E(b) = xa*A21 ^ xb*A22 ^ xc*A23 ^ S(b);
E(c) = xa*A31 ^ xb*A32 ^ xc*A33 ^ S(c);
其中S(a)表示初始状态，E(a)表示a号灯最终的情况，xa表示a号开关是否按下，A13表示3号开关是否影响1号灯的亮灭，异或操作体现了操作的具体影响。
将S项移到方程的左边，我们抽象出系数矩阵，然后构造出增广矩阵，然后就是进行高斯消元，高斯消元的意思可以看作是符合一系列两个逻辑关系的情况 下，对变元要求的变换。只不过这里用的全部都是异或操作，最后我们进行秩的判定，如果矩阵的秩和邻接矩阵的秩不相等的话那么就无解，如果相同的话，那么说 明达到理想灯的亮灭情况下至少需要确定的状态的开关数为矩阵的秩。那么解就是剩下开关的任意选择了，即2^X（每个开关对应关或者是开）。
1 #include<cstdio>
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define Min(a,b) a<b?a:b
12 #define Max(a,b) a>b?a:b
13 #define CL(a,num) memset(a,num,sizeof(a));
14 #define maxn 35
15 #define eps 1e-6
16 #define inf 9999999
17 #define mx 1<<60
18 using namespace std;
19 int mat[maxn][maxn] ;
20 int x[maxn] ;
21 int free_x[maxn] ;
22 int s[maxn],e[maxn] ;
23
24 int gcd(int a,int b)
25 {
26 int t;
27 while(b != 0)
28 {
29 t = b;
30 b = a%b;
31 a = t;
32 }
33 return a;
34 }
35 int lcm(int a,int b)
36 {
37 return (a*b)/gcd(a,b);
38 }
39 int Gauss(int var,int equ)
40 {
41 int i,j,k,col;
42 int max_r;
43 int ta,tb;
44 int LCM;
45 int free_x_num;
46 int free_index;
47 int tmp ;
48
49 for(k = 0 , col = 0;k < equ && col < var;k ++,col++)
50 {
51 max_r = k;
52 for(i = k + 1; i < equ ;++i)
53 {
54 if(abs(mat[i][col]) > abs(mat[max_r][col]))max_r = i;
55 }
56
57
58
59 if(max_r != k)
60 {
61 for(i = col; i < var+1;++i)//
62 {
63 swap(mat[k][i],mat[max_r][i]);
64 }
65 }
66 if(mat[k][col] == 0)
67 {
68 k--;
69 continue ;
70 }
71
72
73 for(i = k + 1; i < equ;i++)
74 {
75 if(mat[i][col])
76 {
77
78 for(j = col;j < var + 1; j++)
79 {
80
81 mat[i][j] = mat[i][j]^mat[k][j] ;
82
83 }
84 }
85
86 }
87
88 }
89
90
91 for(i = k; i < equ ;i++)//
92 {
93 if(mat[i][col]!= 0) return -1 ;
94 }
95
96 if(k <= var)
97 {
98 return var - k ;
99
100 }
101
102
103 return 0;
104 }
105 int main()
106 {
107 int i,j,num,n,a,b;
108 //freopen("data.txt","r",stdin);
109 int t;
110 scanf("%d",&t);
111 while(t--)
112 {
113 scanf("%d",&n);
114 CL(mat,0);
115 for(i = 0 ; i< n;i++)
116 {
117 scanf("%d",&s[i]);
118 }
119 for(i = 0; i< n;i++)
120 {
121 mat[i][i] = 1;
122 scanf("%d",&e[i]);
123 }
124 for(i = 0 ; i < n;i++)
125 mat[i][n] = s[i]^e[i] ;
126 while(scanf("%d%d",&a,&b),a+b)
127 {
128 mat[b - 1][a - 1] = 1 ;
129
130 }
131
132
133 int ans = Gauss(n,n);
134 if(ans == -1)
135 printf("Oh,it's impossible~!!\n");
136 else printf("%.0f\n",pow(2.0,ans));
137 }
138
139 }
2 #include<cstring>
3 #include<cmath>
4 #include<iostream>
5 #include<algorithm>
6 #include<set>
7 #include<map>
8 #include<queue>
9 #include<vector>
10 #include<string>
11 #define Min(a,b) a<b?a:b
12 #define Max(a,b) a>b?a:b
13 #define CL(a,num) memset(a,num,sizeof(a));
14 #define maxn 35
15 #define eps 1e-6
16 #define inf 9999999
17 #define mx 1<<60
18 using namespace std;
19 int mat[maxn][maxn] ;
20 int x[maxn] ;
21 int free_x[maxn] ;
22 int s[maxn],e[maxn] ;
23
24 int gcd(int a,int b)
25 {
26 int t;
27 while(b != 0)
28 {
29 t = b;
30 b = a%b;
31 a = t;
32 }
33 return a;
34 }
35 int lcm(int a,int b)
36 {
37 return (a*b)/gcd(a,b);
38 }
39 int Gauss(int var,int equ)
40 {
41 int i,j,k,col;
42 int max_r;
43 int ta,tb;
44 int LCM;
45 int free_x_num;
46 int free_index;
47 int tmp ;
48
49 for(k = 0 , col = 0;k < equ && col < var;k ++,col++)
50 {
51 max_r = k;
52 for(i = k + 1; i < equ ;++i)
53 {
54 if(abs(mat[i][col]) > abs(mat[max_r][col]))max_r = i;
55 }
56
57
58
59 if(max_r != k)
60 {
61 for(i = col; i < var+1;++i)//
62 {
63 swap(mat[k][i],mat[max_r][i]);
64 }
65 }
66 if(mat[k][col] == 0)
67 {
68 k--;
69 continue ;
70 }
71
72
73 for(i = k + 1; i < equ;i++)
74 {
75 if(mat[i][col])
76 {
77
78 for(j = col;j < var + 1; j++)
79 {
80
81 mat[i][j] = mat[i][j]^mat[k][j] ;
82
83 }
84 }
85
86 }
87
88 }
89
90
91 for(i = k; i < equ ;i++)//
92 {
93 if(mat[i][col]!= 0) return -1 ;
94 }
95
96 if(k <= var)
97 {
98 return var - k ;
99
100 }
101
102
103 return 0;
104 }
105 int main()
106 {
107 int i,j,num,n,a,b;
108 //freopen("data.txt","r",stdin);
109 int t;
110 scanf("%d",&t);
111 while(t--)
112 {
113 scanf("%d",&n);
114 CL(mat,0);
115 for(i = 0 ; i< n;i++)
116 {
117 scanf("%d",&s[i]);
118 }
119 for(i = 0; i< n;i++)
120 {
121 mat[i][i] = 1;
122 scanf("%d",&e[i]);
123 }
124 for(i = 0 ; i < n;i++)
125 mat[i][n] = s[i]^e[i] ;
126 while(scanf("%d%d",&a,&b),a+b)
127 {
128 mat[b - 1][a - 1] = 1 ;
129
130 }
131
132
133 int ans = Gauss(n,n);
134 if(ans == -1)
135 printf("Oh,it's impossible~!!\n");
136 else printf("%.0f\n",pow(2.0,ans));
137 }
138
139 }