poj 1830 异或方程组

【题意】

有N个相同的开关，每个开关都与某些开关有着联系，每当你打开或者关闭某个开关的时候，其他的与此开关相关联的开关也会相应地发生变化，即这些相联系的开关的状态如果原来为开就变为关，如果为关就变为开。你的目标是经过若干次开关操作后使得最后N个开关达到一个特定的状态。对于任意一个开关，最多只能进行一次开关操作。你的任务是，计算有多少种可以达到指定状态的方法。（不计开关操作的顺序）

【题解】

此题就是要求有多少个解。

对于每个开关，建立一个方程，每个开关使用过与否为未知数。

高斯消元即可

【教训】

重要的是，每一个方程必须和自己关联

【代码】

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
using namespace std;

int a[31],st[31],ed[31];
int m,n;
inline int get(int i,int j)
{
    j--;
    return (a[i]>>j)&1;
}

int gauss() //for xor faster
{
    int row,col,i,id;
    for (row=col=1;row<=m && col<=n;row++,col++)
    {
        id=row;
        for (i=row+1;i<=m;i++)
            if (get(i,col)>get(id,col))
                id=i;
        if (id!=row)
            swap(a[row],a[id]);
        if (get(row,col)==0)
        {
            row--;
            continue;
        }
        for (i=row+1;i<=m;i++)
        {
            if (get(i,col)==0) continue;
            a[i]^=a[row];
        }
    }
    for (i=row;i<=m;i++)
        if (get(i,col)) return 0;
    return 1<<(n-row+1);
}

int main()
{
    freopen("in.txt","r",stdin);
    int i,cc,ans,x,y;
    cin >> cc;
    while (cc--)
    {
        memset(a,0,sizeof(a));
        cin >> n;
        for (i=1;i<=n;i++)
            cin >> st[i];
        for (i=1;i<=n;i++)
            cin >> ed[i];
        while (1)
        {
            cin >> x >> y;
            if (x==0 && y==0) break;
            a[y]^=1<<(x-1);
        }
        for (i=1;i<=n;i++)
        {
            a[i]^=(st[i]^ed[i])<<n;
            a[i]^=1<<(i-1);
        }
        m=n;
        ans=gauss();
        if (ans==0) cout << "Oh,it's impossible~!!\n";
        else cout << ans << endl;
    }
}