链接：http://poj.org/problem?id=1830
某天“佐理慧学姐”突然来问了我这道题。
诶，窝只会线性基，但是好像搞不了方案数啊……
啃题解吧。
woc！线性代数哦，就是那种我不会的东西么。
矩阵的秩是啥啊……*元又是啥啊……
没办法，开始补一波线性代数。
看到一半跑出来A掉了这题。
矩阵的秩啊……可以理解为给你一些线性方程组，然后你会发现x+y=1其实跟2x+2y=2是一样的，那这俩玩意其实就是一个方程，矩阵的秩就是最后真正有用的方程数量。
*元啊……就是解到最后发现有些变量可以随便取咯……
然后本题答案就是$2^{*元个数}$
如果我完全不会线性代数怎么理解这题嘞？
我先找到可以让第一个位置灯状态变化的操作，然后强行钦定内定就由你来点亮这盏灯，把后面可以点亮这盏灯的都异或上它，相当于如果用了那盏灯就再把现在这盏撤销掉，然后异或过的灯就变成两盏灯的组合，然后一直做下去，每个操作就都变成很多操作的组合惹……
最后看下有哪些组合是可有可无的就吼了。
由于行秩和列秩素一样的，所以你在码的时候……把行和列倒过来了也没关系……
#include<cstring>
#include<cstdio>
#include<algorithm>
#define MN 200001
using namespace std; int read_p,read_ca,read_f;
inline int read(){
read_p=;read_ca=getchar();read_f=;
while(read_ca<''||read_ca>'') read_f=read_ca=='-'?-:read_f,read_ca=getchar();
while(read_ca>=''&&read_ca<='') read_p=read_p*+read_ca-,read_ca=getchar();
return read_p*read_f;
}
int T,n,m,A,B,MMH;
bool o[],e[],a[][];
int work(){
int i,j,k,l;
for (i=j=;j<n;j++){
for (k=i;k<n;k++)
if (a[k][j]) break;
if (k<n){
for (l=j;l<=n;l++) swap(a[i][l],a[k][l]);
for (l=i+;l<=n;l++)
if (a[l][j]) for (k=j;k<=n;k++) a[l][k]^=a[i][k];
i++;
}
}
for (j=i;j<n;j++) if (a[j][n]) return -;
return <<(n-i);
}
int main(){
register int i;
T=read();
while (T--){
n=read();memset(a,,sizeof(a));
for (i=;i<n;i++) o[i]=read();
for (i=;i<n;a[i][i]=,i++) if (read()!=o[i]) a[i][n]=;
while ((A=read())|(B=read())) a[B-][A-]=;
MMH=work();
if (MMH==-) puts("Oh,it's impossible~!!");else printf("%d\n",MMH);
}
}