[POJ1830]开关问题（高斯消元，异或方程组）

题目链接：http://poj.org/problem?id=1830

题意：中文题面，求的是方案数。

首先可以知道， 如果方案数不止一个的话，说明矩阵行列式值为0，即存在*变元，由于变量只有两种状态，那么方案数就是2^*变元数。

从起始状态到终止状态，只需要关心起始和终止哪些状态不一样就行，也就是翻转奇数次。

由于是倒推，所以开关的影响要反过来存。

 #include <bits/stdc++.h>
 using namespace std;

 typedef long long LL;
 const int maxn = ;
 int equ, var;
 int a[maxn][maxn];
 int x[maxn];
 int free_x[maxn];
 int free_num;

 int gauss() {
     int max_r, col, k;
     free_num = ;
     for(k = , col = ; k < equ && col < var; k++, col++) {
         max_r = k;
         for(int i = k + ; i < equ; i++) {
             if(abs(a[i][col]) > abs(a[max_r][col]))
                 max_r = i;
         }
         if(a[max_r][col] == ) {
             k--;
             free_x[free_num++] = col;
             continue;
         }
         if(max_r != k) {
             for(int j = col; j < var + ; j++)
                 swap(a[k][j], a[max_r][j]);
         }
         for(int i = k + ; i < equ; i++) {
             if(a[i][col] != ) {
                 for(int j = col; j < var + ; j++) {
                     a[i][j] ^= a[k][j];
                 }
             }
         }
     }
     for(int i = k; i < equ; i++) {
         if(a[i][col] != )
             return -;
     }
     if(k < var) return var - k;
     for(int i = var - ; i >= ; i--) {
         x[i] = a[i][var];
         for(int j = i + ; j < var; j++) {
             x[i] ^= (a[i][j] & x[j]);
         }
     }
     return ;
 }

 int main() {
     // freopen("in", "r", stdin);
     int T, _ = ;
     char wtf[] = "Oh,it's impossible~!!";
     scanf("%d", &T);
     while(T--) {
         scanf("%d", &var);
         equ = var;
         memset(a, , sizeof(a));
         memset(x, , sizeof(x));
         memset(free_x, , sizeof(free_x));
         for(int i = ; i < var; i++) {
             scanf("%d", &a[i][var]);
             a[i][i] = ;
         }
         int u, v;
         for(int i = ; i < var; i++) {
             scanf("%d", &u);
             a[i][var] ^= u;
         }
         while(~scanf("%d%d",&u,&v) && u+v) {
             a[v-][u-] = ;
         }
         int ret = gauss();
         if(ret == -) puts(wtf);
         else printf("%lld\n", (LL)((LL) << ret));
     }
     return ;
 }