Description

【题意】0x30数学知识（0x35 高斯消元与线性空间）例题2：开关问题
有 $N$ 个相同的开关，每个开关都与某些开关有着联系，每当你打开或者关闭某个开关的时候，其他的与此开关相关联的开关也会相应地发生变化，即这些相联系的开关的状态如果原来为开就变为关，如果为关就变为开。
你的目标是经过若干次开关操作后使得最后 $N$ 个开关达到一个特定的状态。
对于任意一个开关，最多只能进行一次开关操作。
你的任务是，计算有多少种可以达到指定状态的方法（不计开关操作的顺序）。

【输入格式】
输入第一行有一个数 $K$ ，表示以下有 $K$ 组测试数据。
每组测试数据的格式如下：
第一行 一个数 $N$（$0 < N < 29$）。
第二行 $N$ 个0或者1的数，表示开始时 $N$ 个开关状态。
第三行 $N$ 个0或者1的数，表示操作结束后 $N$ 个开关的状态。
接下来 每行两个数$I J$，表示如果操作第 $I$ 个开关，第 $J$ 个开关的状态也会变化。
每组数据以 0 0 结束。

【输出格式】
如果有可行方法，输出总数，否则输出“Oh,it's impossible~!!” 。

【输入样例】
2
3
0 0 0
1 1 1
1 2
1 3
2 1
2 3
3 1
3 2
0 0
3
0 0 0
1 0 1
1 2
2 1
0 0

【输出样例】
4
Oh,it's impossible~!!

Hint

#include <bits/stdc++.h>
using namespace std;
int n,a[35][35];
void gauss()
{
	int r=1;
    for(int c=1;c<=n;c++)
    {
        for(int i=r+1;i<=n;i++)
		{
			while(a[i][c])
			{
				//这里没有倍数bs，异或的本质就没有进位的二进制加法
				for(int j=1;j<=n+1;j++)a[r][j]=a[r][j]^a[i][j];
				swap(a[r],a[i]);
			}
		}
		if(a[r][c]!=0)r++;
    }
	for(int i=r;i<=n;i++)if(a[i][n+1]==1) {printf("Oh,it's impossible~!!\n");return ;}
	printf("%d\n",(  1<<( n-(r-1) )  ));
}
int main()
{
    int T;scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		memset(a,0,sizeof(a));
	    for(int i=1;i<=n;i++ )scanf("%d",&a[i][n+1]);
	    for(int i=1,x;i<=n;i++)
	    {
	    	scanf("%d",&x); 
	    	a[i][n+1]^=x;
	    	a[i][i]=1;
	    }
	    int x,y;while(scanf("%d%d",&x,&y)!=EOF && x &&y)a[y][x]=1;
	    gauss();
    }
    return 0;
}