高斯消元--热身题

208.开关问题就是个解异或方程的高斯消元~
思路:就是你把所有要改变的灯置为1,表示要改变.放在增广矩阵的最后一行.然后把和当前灯有关系的开关置为1.然后进行消元,有k个自由源答案就是2^k..
代码如下:

#include <bits/stdc++.h>
using namespace std;
const int N=35;
int a[N][N],n;
int gauss()
{
    int r,c;
    for(r=1,c=1;c<=n;c++)
    {
        int t=r;
        for(int i=r+1;i<=n;i++)
        {
            if(a[i][c])
            {
                t=i;
            }
        }
        if(!a[t][c]) continue;
        for(int i=1;i<=n+1;i++)
        {
            swap(a[t][i],a[r][i]);
        }
        for(int i=r+1;i<=n;i++)
        {
            if(a[i][c])
            {
                for(int j=n+1;j>=c;j--)
                {
                    a[i][j]^=a[r][j];
                }
            }
        }
        r++;
    }

    int res=1;
    for(int i=r;i<=n;i++)
    {
        if(a[i][n+1]) return 0;
        res*=2;
    }
    return res;
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        memset(a,0,sizeof a);
        cin>>n;
        for(int i=1;i<=n;i++) {cin>>a[i][n+1];a[i][i]=1;}
        for(int i=1;i<=n;i++) {int z;cin>>z;a[i][n+1]^=z;}
        int x,y;
        while(cin>>x>>y,x||y) a[y][x]=1;
        int res=gauss();
        if(!res) puts("Oh,it's impossible~!!");
        else     cout<<res<<endl;
    }
    return 0;
}