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

Description

有N個相同的開關，每個開關都與某些開關有着聯系，每當你打開或者關閉某個開關的時候，其他的與此開關相關聯的開關也會相應地發生變化，即這些相聯系的開關的狀态如果原來為開就變為關，如果為關就變為開。你的目标是經過若幹次開關操作後使得最後N個開關達到一個特定的狀态。對于任意一個開關，最多隻能進行一次開關操作。你的任務是，計算有多少種可以達到指定狀态的方法。（不計開關操作的順序）

Input

輸入第一行有一個數K，表示以下有K組測試資料。 

每組測試資料的格式如下： 

第一行 一個數N（0 < N < 29） 

第二行 N個0或者1的數，表示開始時N個開關狀态。 

第三行 N個0或者1的數，表示操作結束後N個開關的狀态。 

接下來 每行兩個數I J，表示如果操作第 I 個開關，第J個開關的狀态也會變化。每組資料以 0 0 結束。 

Output

如果有可行方法，輸出總數，否則輸出“Oh,it's impossible~!!” 不包括引号

Sample Input

2
3
0 0 0
1 1 1
1 2
1 3
2 1
2 3
3 1
3 2
0 0
3
0 0 0
1 0 1
1 2
2 1
0 0
      

Sample Output

4
Oh,it's impossible~!!      

題意：問你從開始的狀态到達最終狀态的方案數      

分析：構造異或矩陣，消元求自由元個數x,答案即為（2^x)      

如何構造矩陣，我們知道n=3有      

E(1)=x1*A(1,1) ^ x2*A(1,2) ^x3*A(1,3) ^S(1)      

E(2)=x1*A(2,1) ^ x2*A(2,2) ^x3*A(2,3) ^S(2)      
   

E(3)=x1*A(3,1) ^ x2*A(3,2) ^x3*A(3,3) ^S(3)      
    
我們稍微做一下變換      
    
即E(i)^S(i)=x1*A(i,1) ^ x2*A(i,2) ^x3*A(i,3)      
    
其他要做的就是高消了。      
    
<pre name="code" class="cpp">#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<string>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
using namespace std;
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define CLEAR( a , x ) memset ( a , x , sizeof a )
const int INF=0x3f3f3f3f;
typedef long long LL;
const int maxn=20000+100;
const int mod=1e9+7;
int t,n;
int st[35],ed[35];
int mp[35][35];
int equ,var;
int X[35],free_x[35];
int free_num,N;
int Gauss()
{
    int max_r,col,k;
    free_num=0;
    for(k=0,col=0;k<equ&&col<var;k++,col++)
    {
        max_r=k;
        for(int i=k+1;i<equ;i++)
        {
            if(abs(mp[i][col])>abs(mp[max_r][col]))
                max_r=i;
        }
        if(mp[max_r][col]==0)
        {
            k--;
            free_x[free_num++]=col;
            continue;
        }
        if(max_r!=k)
        {
            for(int j=col;j<var+1;j++)
                swap(mp[k][j],mp[max_r][j]);
        }
        for(int i=k+1;i<equ;i++)
        {
            if(mp[i][col]!=0)
            {
                for(int j=col;j<var+1;j++)
                    mp[i][j]^=mp[k][j];
            }
        }
    }
    for(int i=k;i<equ;i++)
        if(mp[i][col]!=0)  return -1;
    return var-k;
}
int main()
{
    int x,y;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        CLEAR(mp,0);
        REP(i,n) scanf("%d",&st[i]);
        REP(i,n) scanf("%d",&ed[i]);
        while(~scanf("%d%d",&x,&y)&&(x+y))
            mp[y-1][x-1]=1;
        REP(i,n)
        {
            mp[i][n]=st[i]^ed[i];
            mp[i][i]=1;
        }
        equ=n,var=n;
        int ans=Gauss();
        if(ans==-1)
            puts("Oh,it's impossible~!!");
        else
            printf("%d\n",1<<ans);
    }
    return 0;
}