(より詳しい解説は後日ブログで公開します)

必要なら孤立点を追加して \(N = 2L\) が偶数であるとします．

マッチングに \(L\) 辺 \((1, 2), \ldots, (2L-1, 2L)\) を追加したグラフを考えてそれを数えることにします．各連結成分はサイクルまたはパスとなり，その頂点集合は追加した辺の集合に対応します．

追加した \(L\) 辺全体の各部分集合ごとに，作れるサイクルやパスが何通りあるかは DP で \(O(2^{N/2} N^2)\) 時間ですべて計算できます (例えば，サイクルやパスの中の最大の番号の頂点から辿ります)．

この結果を集合冪級数で表し，\(\mathit{cycle}, \mathit{path}\) とします．問題 Fast as Ryser の解法は，これらを重み付きで求めて \(\exp(\mathit{cycle} + \mathit{path})\) を計算するというものです．

マッチングの大きさがパスの個数で決まることに注目すると，本問では各 \(k\) に対して \(\exp(\mathit{cycle}) \frac{\mathit{path}^k}{k!}\) の 全体集合 (\(L\) 元) における係数を求めればよいということになります．\(\exp(\mathit{cycle})\) は \(O(2^{N/2} N^2)\) 時間で計算できます．

転置原理を用いると，\(f_0, f_1, \ldots\) が与えられて \(\sum_k f_k \frac{\mathit{path}^k}{k!}\) の \(2^L\) 個の係数すべてを求める問題に帰着されます．これは https://codeforces.com/blog/entry/92183 の手法で \(O(2^{N/2} N^2)\) 時間で解けるので，転置する前も同じ計算量で解けます．

なお，\(\exp(\mathit{cycle})\) や \(\frac{\mathit{path}^k}{k!}\) はその組合せ的意味を考えてもわかるように \(k!\) が可逆でなくとも環演算のみで定義でき，この問題で必要な計算はすべて環演算のみで行うことができます．