開關問題
Time Limit: 1000MS
Memory Limit: 30000K
Total Submissions: 6021
Accepted: 2290
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~!!
Hint
第一組數據的說明：
一共以下四種方法：
操作開關1
操作開關2
操作開關3
操作開關1、2、3 （不記順序）
Source
LIANGLIANG@POJ
注意：題目中i和j說反了
每個燈可以控制自己和其他的一些燈，xi代表第i個燈是否操作，所以xi的值只會是0或1。
對每一個燈的來說，肯能會收幾個燈的控制，如果第i個燈被第k個燈控制，那麼xk的系數為1，否則為0,。結果如果變化為1，不變化為0，所以得到一個異或方程組。
求解這個異或方程組，進行高斯消元
異或方程組的高斯消元的方式，和不同的高斯消元大部分相同，但是不是用減，而是判斷要消的那行如果是1，進行異或，否則不動。
通過高斯消元，可以判斷出方程是否有解，和解的個數。
如本題中求出矩陣的自由元數num1個。所以這num1個值的取值對結果是沒有影響的，又因為xi只能取0或1，所以方法數位2^num1
#include
#include
#include
using namespace std ;
int Map[30][30] , a[30] ;
void swap1(int p,int q,int n)
{
int j , temp ;
temp = a[p] ; a[p] = a[q] ; a[q] = temp ;
for(j = 1 ; j <= n ; j++)
{
temp = Map[p][j] ; Map[p][j] = Map[q][j] ; Map[q][j] = temp ;
}
return ;
}
int solve(int n)
{
int i , j , k , t = 1 , num1 = 0 ;
for(i = 1 ; i <= n && t <= n ; i++)
{
for(j = i ; j <= n ; j++)
if( Map[j][t] )
break ;
if(j == n+1)
{
t++ ;
i-- ;
num1++;
continue ;
}
if( i != j )
swap1(i,j,n) ;
for(j = i+1 ; j <= n ; j++)
{
if( Map[j][t] == 0 ) continue ;
for(k = t ; k <= n ; k++)
Map[j][k] = Map[i][k] ^ Map[j][k] ;
a[j] = a[i] ^ a[j] ;
}
t++ ;
}
for( ; i <= n ; i++)
if( a[i] == 1 )
return -1 ;
return num1 ;
}
int main()
{
int t , n , i , j , x ;
scanf("%d", &t) ;
while( t-- )
{
memset(Map,0,sizeof(Map)) ;
scanf("%d", &n) ;
for(i = 1 ; i <= n ; i++)
{
scanf("%d", &a[i]) ;
Map[i][i] = 1 ;
}
for(i = 1 ; i <= n ; i++)
{
scanf("%d", &x) ;
a[i] = a[i]^x ;
}
int u , v ;
while( scanf("%d %d", &v, &u) )
{
if( u == 0 && v == 0 ) break ;
Map[u][v] = 1 ;
}
x = solve(n) ;
if( x == -1 )
printf("Oh,it's impossible~!!\n") ;
else
printf("%d\n", 1<
