Codeforces Round #382 (Div. 1) D. Permutations
問題文が誤解を生みかねない感じがしたので、もとの問題文を変更して問題概要を書きました。
問題概要
完全二部マッチングの問題である。i 番目の辺を削除したときの完全二部マッチングの総数の偶奇を出力せよ。 与えられるグラフは奇数個の完全マッチングを持つことが保証されている。
解法
日本勢にとっては以下の問題は記憶に新しいだろう。
C: 鯛焼き - AtCoder Regular Contest 054 | AtCoder
二部グラフを表現する行列というのを
- A[i][j] = 左側の i 番目の頂点と右側の j 番目の頂点の間に辺がある
として定義する。このとき、このグラフの完全マッチングの総数の偶奇は、この行列の行列式の偶奇と一致する。
そもそも行列式は、n×nのマスから行番号と列番号が被らないように n 個の要素を持ってきて積をとったもの（に+か-を掛けたもの）の総和である。 n個の要素の持ってくる方法は下図のような感じ。
本来マイナスするべきものをプラスにすれば、これは完全マッチングの総数になることが分かる。 mod 2 で考えるとプラスもマイナスも変わらないので、完全マッチングの総数の偶奇は行列式と一致することが示された。
辺(i,j)を消したときの完全マッチングの総数は、消す前の完全マッチングの総数から(i,j)を使う完全マッチングの総数を引けば求まる。
(i,j)を使う完全マッチングの総数というのは、下図オレンジ部の行列式の値と一致する（下図はi=4,j=4の場合）。
これは余因子と呼ばれ、逆行列の各成分から分かる情報である。
したがって逆行列を求めることができれば、問題を解くことができる。
技巧的な問題として逆行列の求め方がある。通常O(N3)なのだが、ブール値での行列式は bitset が使えるので O(N3/64) 時間となり間に合う。
初期状態で奇数個のマッチングを持つという情報を見落としていて、無駄に複雑に考えてしまった。
ちなみにブール値の行列積も O(N^2/64)でできる。
