poj1830开关问题——异或高斯消元

题目：http://poj.org/problem?id=1830

根据题意，构造出n元方程组：

a(1,1)x1 ^ a(1,2)x2 ^ a(1,3)x3 ... a(1,n)xn = st1 ^ ed1

a(2,1)x1 ...... = st2 ^ ed2

......

其中a(x,y)表示x是否受到y影响；x为各灯是否操作；stx为x初始状态，edx为x目标状态；

把一个方程压缩成一个整数，第1位表示等号右边，之后各位表示方程各项；

进行异或运算的高斯消元，要消元时只需异或一下即可；

自由元的存在使其方案数增多，每个自由元使答案*2(可以选择操作或不操作)。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int t,n,a[35],ans;
void gauss()
{
    ans=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=i+1;j<=n;j++)//i+1,不可把之前的a找出来 
            if(a[j]>a[i])swap(a[i],a[j]);
        if(a[i]==0)//i-1个a消掉所有系数，有n-(i-1)个自由元 
        {
            ans=(1<<(n-i+1));break;
        }
        if(a[i]==1)//系数0，常数1 
        {
            ans=0;break;
        }
        //消去其他式中a[i]最高位1
        for(int k=n;k;k--) 
            if(a[i]&(1<<k))
            {
                for(int j=1;j<=n;j++)
                    if(i!=j&&(a[j]&(1<<k)))a[j]^=a[i];
                break;
            }
    }
}
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        memset(a,0,sizeof a);
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]);
        for(int i=1,d;i<=n;i++)
        {
            scanf("%d",&d);
            a[i]^=d;
            a[i]|=(1<<i);
        }
        int x,y;
        while(~scanf("%d%d",&x,&y))
        {
            if(!x&&!y)break;
            a[y]|=(1<<x);
        }
        gauss();
        if(!ans)printf("Oh,it's impossible~!!
");
        else printf("%d
",ans);
    }
    return 0;
}