ARC054 C - たい焼き

問題文

http://arc054.contest.atcoder.jp/tasks/arc054_c

解法

2部グラフの完全マッチングの個数の偶奇性を問う問題．
当然数え上げるのは大変．しかし偶奇だけなら，行列式でわかる．

与えられた隣接行列を Aとする．
すると，完全マッチングの個数 M は，A のパーマネントに等しい事がわかる．
パーマネントを求めるのは困難だが，偶奇だけなら，行列式に一致する．
行列式は，パーマネントに置換の符号がついたものである．置換の符号は -1 か 1 だから，mod 2 の上ではこれらはともに 1 に等しく，隣接行列は，mod 2 上で行列式とパーマネントが一致する．

行列式は O(n^3) でもとまるので，これでACをもらうことができる．

ソースコード

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

bool det(vector<vector<int>> v) {
    const int n = v.size();
    bool res = 1;
    for(int i = 0; i < n; ++i) {
        int pivot = i;
        for(int j = i + 1; j < n; ++j) {
            if(v[j][i]) {
                pivot = j;
            }
        }
        swap(v[pivot], v[i]);
        res &= v[i][i];
        if(!v[i][i]) {
            break;
        }
        for(int j = i + 1; j < n; ++j) {
            for(int k = n - 1; k >= i; --k) {
                v[j][k] = v[j][k] ^ v[i][k] & v[j][i];
            }
        }
    }
    return res;
}

int main() {
    int N;
    cin >> N;
    vector<vector<int>> v(N, vector<int>(N));
    for(int i = 0; i < N; ++i) {
        for(int j = 0; j < N; ++j) {
            char c;
            cin >> c;
            v[i][j] = c == '1';
        }
    }
    if(det(v)) {
        cout << "Odd" << endl;
    } else {
        cout << "Even" << endl;
    }
}

感想

有名事実らしいが，本番でこれを導き出せる人はすごいと思う．