题目背景
某些开关的动作可能影响另一些开关的状态，因此以开关为节点，如果存在这种关系就加入一条有向边，这样就构成了一个图，可以用邻接矩阵表示。当某个开关按下时，其自身状态改变，受其影响的开关的状态也改变。
题目描述
有 N 个相同的开关，每个开关都与某些开关有着联系，每当你打开或者关闭某个开关的时候，其他的与此开关相关联的开关也会相应地发生变化，即这些相联系的开关的状态如果原来为开就变为关，如果为关就变为开。你的目标是经过若干次开关操作后使得最后 N 个开关达到一个特定的状态。对于任意一个开关，最多只能进行一次开关操作。你的任务是，计算有多少种可以达到指定状态的方法。（不计开关操作的顺序）
输入格式： 第一行有一个数 K，表示以下有 K 组测试数据。 每组测试数据的格式如下：
- 第一行 一个数 N（0 < N < 29）
- 第二行 N 个 0 或者 1 的数，表示开始时 N 个开关状态。
- 第三行 N 个 0 或者 1 的数，表示操作结束后 N 个开关的状态。
- 接下来 每行两个数 I J，表示如果操作第 I 个开关，第 J 个开关的状态也会变化。每组数据以 0 0 结束。
输出格式： 如果有可行方法，输出总数，否则输出 "Oh,it's impossible~!!"
思路分析
用两个 N 维向量表示初始状态和结束状态，两者逐个元素异或，就得到了开关状态的变化。
以第一个样例输入为例分析，3 个开关，两两相连，初始状态 000，最终状态 111，开关对应的邻接矩阵为
将对角线的 0 全部换成 1，得矩阵 A。将矩阵每一列想象为一个开关按下后产生的效果（1 表示状态翻转，0 表示不变），比如，第二列就表示按下第二个开关，则第二个开关的本身状态要改变（这就是把对角线 0 换成 1 的原因），受第二个开关影响的开关 j 状态也要改变，恰好对应邻接矩阵中 A[j, 2]=1。
把 A 写成分块矩阵的形式，每一列作为一个子矩阵，则有 A=[a1,a2, a3],此处 ai 均为列向量，设第 i 个开关按下次数为 xi，xi=0 或 1（开关按两下和没按是等效的，0/1 就够了）。
记初始状态 b0=[0,0,0],最终状态 b1=[1,1,1],则状态变化 b=b0^b1=[1,1,1],这里 b 也是列向量。目标就是求 x1a1 + x2a2 +x3a3 = b 的解的个数（此处的加是模 2 加，也就是异或，下同）。
这个方程可以写成线性方程组形式。下面就是解这个线性方程组。
对增广矩阵 [A b] 做初等行变换，化成阶梯形（高斯消元法）。如果存在 [0,0,…,0,1] 的行，就是无解；如果存在 r 行 [0,0,…,0,0]，就意味着有 r 个自由变量，因为这里的变量只取 0/1，所以有 2^r 个解；如果不存在 [0,0,…,0,*]，即把最后一行去掉后不存在全 0 行，则 A 为满秩矩阵，则方程组有唯一解。
如果不理解这个地方，建议找本线性代数书，看一下线性方程组的解法，解的结构，通解。
参考实现
#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string.h>
#include <math.h>
using namespace std;
const int MAXN = 50;
const int mod = ;
a[MAXN][MAXN];
x[MAXN];
free_x[MAXN];
{
t;
(b != ) {
t = b;
b = a % b;
a = t;
}
a;
}
{
a / (a, b) * b;
}
{
i, j, k;
max_r;
col;
ta, tb;
LCM;
temp;
free_x_num;
free_index;
( i = ; i <= var; i++) {
x[i] = ;
free_x[i] = ;
}
col = ;
(k = ; k < equ && col < var; k++, col++) {
max_r = k;
(i = k + ; i < equ; i++) {
((a[i][col]) > (a[max_r][col])) max_r = i;
}
(max_r != k) {
(j = k; j < var + ; j++) (a[k][j], a[max_r][j]);
}
(a[k][col] == ) {
k--;
;
}
(i = k + ; i < equ; i++) {
(a[i][col] != ) {
LCM = ((a[i][col]), (a[k][col]));
ta = LCM / (a[i][col]);
tb = LCM / (a[k][col]);
(a[i][col] * a[k][col] < ) tb = -tb;
(j = col; j < var + ; j++) {
a[i][j] = (mod + (a[i][j] % mod) * ta - (a[k][j] % mod) * tb) % mod;
}
}
}
}
(i = k; i < equ; i++) {
((a[i][col] % mod) != ) ;
}
(k < var) {
(i = k - ; i >= ; i--) {
free_x_num = ;
(j = ; j < var; j++) {
(a[i][j] != && free_x[j]) free_x_num++, free_index = j;
}
(free_x_num > ) ;
temp = a[i][var];
(j = ; j < var; j++) {
(a[i][j] != && j != free_index) temp -= a[i][j] * x[j];
}
x[free_index] = temp / a[i][free_index];
free_x[free_index] = ;
}
var - k;
}
(i = var - ; i >= ; i--) {
temp = a[i][var];
(j = i + ; j < var; j++) {
(a[i][j] != ) temp -= a[i][j] * x[j];
}
(temp % a[i][i] != ) ;
x[i] = temp / a[i][i];
}
;
}
{
T;
(, &T);
equ, var;
st[], ed[];
ii, jj;
(T--) {
(, &equ);
var = equ;
( i = ; i < equ; i++) (, &st[i]);
( i = ; i < equ; i++) (, &ed[i]);
(a, , (a));
(~(, &ii, &jj) && ii) a[jj - ][ii - ] = ;
( i = ; i < equ; i++) a[i][i] = ;
( i = ; i < equ; i++) a[i][equ] = (st[i] + ed[i]) % mod;
free_sum = (equ, var);
(free_sum < ) ();
(, << free_sum);
}
;
}
