# Hafnian of Matrix

## 概要
https://judge.yosupo.jp/problem/hafnian_of_matrix

多重辺ありの $N=2L$ 頂点無向グラフが与えられるので、完全マッチングの個数を $O(2^NN^2)$ で数える。

## 前提知識
- 集合冪級数
https://nyaannyaan.github.io/library/set-function/subset-convolution.hpp.html
https://hos-lyric.hatenablog.com/entry/2021/01/14/201231
https://codeforces.com/blog/entry/92128

簡潔に言うと、$\{1,\ldots,n\}$ の部分集合 $\mathcal{P}$ から体 $\mathbb{K}$ への写像 $f$ を冪級数 $\sum_{S \in \mathcal{P}} a_S x^S$ の形で表し、写像の和を各点和、積をsubset convolution $f*g=\sum_{S \sqcup T=A}f(S) g(T) x^A$ として定めたもの。
形式的冪級数と同様に適切な条件下で inv,log,exp などの操作も定義でき、 $O(2^nn^2)$ で計算できる。

## 解法

$(1,2),\ldots,(2L-1,2L)$ の辺を追加したグラフを考える。
このとき、完全マッチングはいくつかのサイクルに分割される。(次数は全て2なので)

先に $\{(1,2),\ldots,(2L-1,2L)\}=E$ の各部分集合 $S$ について、$S$ を全て使うような一閉路の個数を求める。これは

$DP[S][v]:=$ $S$ を使った辺集合、「$S$ に含まれる頂点のうち最大の番号のものと $v$ 」をパスの端点としたときのパスの個数

というbitDPによって計算できる。(計上するときにパスの端点をくっつけることにする)
数えるサイクルが重複しないように先に番号最大の頂点をfixしているので、遷移先の $v$ は $S$ のtopbitを更新しないことに注意する。

$S$ に対してサイクルの個数を返す写像を集合冪級数 $cycle$ とみなすと、計算したいものは $\sum_{S_1 \sqcup \cdots \sqcup S_k=E} \frac{1}{k!} \Pi_{i=1}^k cycle(S_i)=[x^E]\exp(cycle)$ と書けるので、全体の計算量も $O(2^NN^2)$ で行える。