题目链接：http://poj.org/problem?id=1830
给一系列的开关，某两个开关之间存在依赖关系，求从原始状态到最终状态最多有多少种取值方式，这个问题可以转化成求解异或方程组的问题，异或方程组的求解可以从最大主元开始，把其余方程中这个元全部删去，最终可能得到一个右对角的矩阵，而每个等式的值都是零或者一，所以容易得到这个异或方程的解是唯一的，所以初始的时候ans就要设置成1。如果在求解的过程中，最大主元对应的方程已经全都是零了，那么下面的方程一定都是0，这时候一定会产生n-i+1个自由元，他们每个可以取0、1，所以此时有1<<(n-i+1)种可能，如果遇到某一个方程是0=1，那么这个问题无解，ans=0。
代码：
#include<iostream> #include<string.h> using namespace std; const int maxn = 50; int a[maxn]; int main(){ int t; cin>>t; while(t--){ memset(a,0,sizeof(a)); int n; cin>>n; for(int i=1;i<=n;i++)cin>>a[i]; for(int i=1,j;i<=n;i++){ cin>>j; a[i]^=j;//start_i^end_i a[i]|=(1<<i);//a[i][i]=1 } int t,b; while(cin>>t>>b &&!(t==0 && b==0)){ a[b]|=(1<<t);//a[b][t]=1; } int ans=1; for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++){//寻找主元最大的行 if(a[j]>a[i])swap(a[j],a[i]); } if(a[i]==0){//下面所有的异或方程系数都是0，上面的方程都已经确定 ans=1<<(n-i+1); break; } if(a[i]==1){//遇到0=1的情况，无解 ans=0; break; } for(int j=n;j;j--){//寻找最大主元 if((a[i]>>j)&1){ for(int k=1;k<=n;k++){ if(i!=k && (a[k]>>j & 1))a[k]^=a[i]; } break; } } } if(ans==0)cout<<"Oh,it's impossible~!!"<<endl; else cout<<ans<<endl; } }
