高斯消元入门③-异或线性方程,无解,*元,计数-POJ1830

题目大意:

给你 n ( n ≤ 29 ) n(n \leq 29) n(n≤29)个开关。每个开关改变状态会跟着改变其他若干个开关的状态。给你一个开始状态 S S S，一个结束状态 T T T。问你有多少种操作方案使得状态从 S S S到 T T T.(每个开关至多改变一次状态，且无视操作顺序).

题目思路:

套路与POJ1222几乎一样。将每个开关按或不按设成未知数,列出异或线性方程求解即可。

这里关键对解的存在性进行讨论:

答案是 2 f r e e 2^{free} 2free. f r e e free free代表*元的个数.

1.如何求*元：（*元的含义是：可以取定义域中的任何值的未知数，且只有方程中所有*元确定了值之后才能确定所有的未知数.）
当高斯消元的过程中发现某一行的列以下全为0.那么该未知数是*元。

2.如何判断无解的情况.

若跑完高斯消元后剩下的几行中出现 0 , 0 , . . . , x ( x ≠ 0 ) 0 , 0 , ... ,x(x \neq 0) 0,0,...,x(x​=0)的情况。则无解.

AC代码:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <map>
#include <climits>
#include <cassert>
using namespace std;
#define ll long long
const int maxn = 31;
vector<int> in[maxn];
int s[maxn] , t[maxn] , n;
int a[maxn][maxn];
ll ksm (ll a , ll b){ ll ans = 1 , base = a;
while (b){if (b & 1) ans = ans * base;b >>= 1;base = base * base;}return ans;}
int main()
{
    ios::sync_with_stdio(false);
    int tt; cin >> tt;
    while(tt--){
        cin >> n;
        memset(a , 0 , sizeof a);
        for (int i = 1 ; i <= n ; i++) in[i].clear() , in[i].push_back(i);
        for (int i = 1 ; i <= n ; i++) cin >> s[i];
        for (int i = 1 ; i <= n ; i++) cin >> t[i];
        int x , y;
        int free = 0;
        while (cin >> x >> y , x && y) in[y].push_back(x);
        for (int i = 1 ; i <= n ; i++) a[i][n + 1] = s[i] ^ t[i];
        for (int i = 1 ; i <= n ; i++)
            for (int j = 0 ; j < (int)in[i].size() ; j++)
                a[i][in[i][j]] = 1;
        int r , c;
        for (r = c = 1 ; r <= n && c <= n ; r++ , c++){
            int p = 0;
            for (int j = r ; j <= n ; j++){
                if (a[j][c] == 1) {
                    p = j;
                    break;
                }
            }
            if (!p){
                r--;
                free++; // *元个数增多
                continue;
            }
            swap(a[r] , a[p]);
            for (int j = 1 ; j <= n ; j++){
                if (j == r) continue;
                if (a[j][c] == 0) continue;
                for (int k = c ; k <= n + 1 ; k++){
                    a[j][k] ^= a[r][k];
                }
            }
        }
        // 判断不可解
        bool gg = false;
        for (int i = r ; i <= n ; i++)
            if (a[i][n + 1]) gg = true;
        if (gg){
            cout << "Oh,it's impossible~!!" << endl;
            continue;
        }
        cout << ksm(2 , free) << endl;
    }
    return 0;
}