POJ 1830 開關問題 高斯消元 異或方程

題意：給出N個開關，當改變一個開關的狀态時，會改變其他某些開關的狀态。給定開關的初始狀态和最終狀态，問是否有方法從初始狀态到最終狀态。如果有的話，求出方案數。

思路：開關問題，考慮高斯消元解異或方程組。

            這裡需要考慮無解和多解的情況：1.無解，某方程的系數都為0，但是常數項為0. 2.多解，方程的系數為0，同時常數項為0。這樣，有S個自由元（因為取值隻能為0，1）就會有2^S中方案。

代碼如下：

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>

using namespace std;

const int MAXN = 40;

//a is a coff matrix
//l[i] is false which represent free variable res represent the number of free varibles
//ans store the answer

int a[MAXN][MAXN],ans[MAXN];
bool l[MAXN];

int guass(int a[][MAXN],bool l[],int n)
{
    int res = 0, r = 0;
    memset(l,0,sizeof(bool) * n);
    for(int i = 0; i < n; ++i){
        for(int j = r; j < n; ++j){
            if(a[j][i] == 1){
                for(int k = i; k <= n; ++k)
                    swap(a[j][k],a[r][k]);
                break;
            }
        }
        if(a[r][i] == 0){
            if(a[r][n] != 0) return -1;//no solution
            else{// free varbiable
                ++res;continue;
            }
        }
        for(int j = 0; j < n; ++j){
            if(j != r && a[j][i] == 1){;
                for(int k = i; k <= n; ++k)
                    a[j][k] ^= a[r][k];
            }
        }
        l[i] = true,++r;
    }
    return 1<<res;
}

int main(void)
{
    //freopen("main.in","r",stdin);
    int T,N,s,u,v;
    scanf("%d",&T);
    while(T--){
        memset(a,0,sizeof(a));
        scanf("%d",&N);
        for(int i = 0; i < N; ++i)
            scanf("%d",&a[i][N]);
        for(int i = 0; i < N; ++i){
            scanf("%d",&s);
            a[i][N] ^= s;
            a[i][i] = 1;
        }
        while(scanf("%d %d",&u,&v),u||v){
            --u,--v;
            a[v][u] = 1;
        }
        int ans = guass(a,l,N);
        if(ans == -1)
            puts("Oh,it's impossible~!!");
        else
            printf("%d\n",ans);
    }
    return 0;
}