https://atcoder.jp/contests/abc327/editorial/7593 同時期に執筆された、本解説とほとんど同じ方針のユーザー解説です。こちらで説明を省略した部分についても説明があります。

\(a(n, m)\) を \(n\) 頂点 \(m\) 辺の単純とは限らない二部グラフの個数と定義します。\(b(n, m)\) を、\(n\) 頂点 \(m\) 辺の単純とは限らないグラフであって頂点が白黒に塗られており、各辺は異なる色の頂点を結んでいるものの個数と定義します。ただしいずれも頂点と辺にはラベルが付いているものとして数えます。

これらに対する指数型母関数

\[ A = \sum_{n, m} \frac{a(n, m)}{n!m!} x^n y^m \\ B = \sum_{n, m} \frac{b(n, m)}{n!m!} x^n y^m \\ \]

を考えると、\(A ^2 = B\) の関係式が成り立ちます。これは公式解説にもある通り、各連結成分について最も番号の小さい頂点が白と黒のどちらに塗られているかによって連結成分を分類することで証明できます。

さて、単純な考察により、\(b(n, m)\) は以下の式で与えられることが分かります

\[ b(n, m) = \sum_{s + t = n} \binom{n}{s} (st)^m \]

すると \(B\) は以下の式で表されます

\[ B = \sum_{s, t} \frac{x^{s+t}\exp(sty)}{s!t!} \]

我々の目標は \(a(N, M) = N! M! [x^Ny^M]\sqrt{B}\) を求める事でしたが、この \(B\) の平方根を直接計算するには \(M\) が大きすぎます。そこで一旦 \(z = \exp(y)\) と置き代え、以下の式を得ます。

\[ B = \sum_{s, t} \frac{x^{s+t}z^{st}}{s!t!} \]

この変換によって \([x^n]B\) は \(z\) について高々 \(n^2\) 次の多項式になりました。 \(s^2 + t^2 \leq (s+t)^2\) に注意すると帰納的に、\([x^n] \sqrt{B}\) も \(z\) について高々 \(n^2\) 次の多項式となることが分かります。 よって \(\sqrt{B}\) を \(x\) について \(N\) 次まで計算することで、以下のように \([x^N]A\) を \(z (= \exp(y))\) についての多項式として表現したものが得られます。

\[ [x^N]A = \sum_{i = 0}^{N^2} c_i z^i = \sum_{i=0}^{N^2} c_i \exp(iy) \]

従って

\[ a(N, M) = N!M![x^Ny^M]A = N! \sum_{i=0}^{N^2} c_i i^M \]

であり、容易に計算できます。 全体の時間計算量は \(\sqrt{B}\) の計算にどのようなアルゴリズムを使うか次第ですが、\(B\) が疎であることを利用して微分方程式を立てれば、FFT を用いずに \(\Theta(n^5 + n^2 \log(M))\) のアルゴリズムが得られます。