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; } }
感想
有名事実らしいが,本番でこれを導き出せる人はすごいと思う.