問題

$N$ 個のタイヤと $N$ 本の木の完全マッチングの個数パターン数の偶奇を求める。

考察

完全マッチングの数え上げは、01行列のpermanent値に一致し、これはNP困難であることが知られている。行列 $A$ のpermanent値は

${\rm perm}(A) = \sum_{\sigma \in S_n} \prod_{i=1}^n a_{i, \sigma(i)}$

ここで、 $A$ のdeterminant値を見てみると、

${\rm det}(A) = \sum_{\sigma \in S_n} {\rm sgn}(\sigma)\prod_{i=1}^n a_{i, \sigma(i)}$

${\rm sgn}(\sigma)$ は $\pm 1$ なので、どちらも $\mod 2$ で $1$ なのでこれらの値は一致する。 ${\rm det}(A)$ は上三角行列を作れば $\mathcal{O}(N^3)$ で求められる。