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;
    }
}

感想

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