D 問題で利用した考察を応用すると、この問題の答えは次の問題の答えを \(2^M\) 倍したものが答えになると分かります。

\(N\) 頂点 \(M\) 辺の(単純とは限らない)二部グラフの個数を求めよ。ただし、頂点には \(1\) から \(N\) の、辺には \(1\) から \(M\) のラベルがついているとする。

以下では上記の問題の答えを \(a(N, M)\) として、\(a(N, M)\) を高速に計算する方法を説明します。

単純二部グラフの数え上げへの帰着

\(a(N, M)\) の計算は、実は(頂点ラベル付き) 単純二部グラフの数え上げに帰着させることが出来ます。

\(a(N, M)\) の数える対象であるグラフに対して、そのグラフの多重辺を全て 1 本とみなした時に出来る単純二部グラフが 1 個対応しています。また、

• \(b(M, k)\) : \(k\) 個の区別された箱に \(M\) 個の区別されたボールを入れる方法の通り数

とすると、\(k\) 辺の単純二部グラフに対して、 \(a(N, M)\) の数える対象がちょうど \(b(M, k)\) 個対応しています。よって、

• \(f(N, M)\) : \(N\) 頂点 \(M\) 辺の頂点ラベル付き単純二部グラフの個数

とすると、\(L = \lfloor N/2 \rfloor \lceil N/2 \rceil\) (\(=\) \(N\) 頂点の二部グラフの辺数の最大) として

\[a(N, M) = \sum_{k=0}^{L}f(N, k) b(M, k)\]

という関係式が成り立ちます。また、\(b(M, k)\) は第 2 種スターリング数 \(S(M, k)\) に \(k!\) を乗じたもので

\[b(M, k) = \sum_{i=1}^k (-1)^{k-i} \binom{k}{i} i^M\]

であると確認できるので、\(b(M, \ast)\) は \(\mathrm{O}(N^4 \log M)\) 程度で列挙できます。

以上より、\(a(N, M)\) を計算する問題を \(f(N, 0), f(N, 1), \dots, f(N, L)\) を列挙する問題に帰着させることが出来ました。

単純二部グラフの数え上げ

\(f(N,0), f(N,1), \dots, f(N,L)\) の列挙、すなわち単純二部グラフの数え上げは、俗に除原理 DP と呼ばれる DP を利用して行うことが出来ます。除原理 DP については ABC213 の解説 などで触れられているのでそちらを参考にしてみてください。

まず、\(g(n, m)\) \((1 \leq n \leq N, 1 \leq m \leq L)\) を次のように定義します。

• \(g(n, m) :=\) (各頂点に白か黒の色が塗られていて、同じ色の頂点同士を結ばないように辺が張られている \(n\) 頂点 \(m\) 辺の単純グラフの個数)

すると、\(g(n, m)\) は次の値になるので数えられます。

\[g(n, m) = \sum_{i=0}^n \binom{n}{i} \binom{i(n-i)}{m}\]

ここから DP によって「連結」という条件を加えた場合を計算します。
\(h(n, m)\) \((1 \leq n \leq N, 1 \leq m \leq L)\) を次のように \(g\) の定義に連結性を加えたものとして定義します。

• \(h(n, m) :=\) (各頂点に白か黒の色が塗られていて、同じ色の頂点同士を結ばないように辺が張られている \(n\) 頂点 \(m\) 辺の単純 連結 グラフの個数)

とすると、除原理の発想により次の式を得られ、\(h(n, m)\) を添え字昇順に DP で計算していくことができます。

\[h(n, m) = g(n, m) - \sum_{1 \leq i \lt n} \sum_{0 \leq j \leq m} \binom{n-1}{i-1} h(i, j) g(n-i,m-j)\]

ここで \(1\) つの単純連結二部グラフに \(2\) つの \(h\) で数える対象が対応しているのに気付くと、次の事実を得られます。

• \(\dfrac{h(n, m)}{2} =\) (\(n\) 頂点 \(m\) 辺の 単純連結二部グラフ の個数)

よって、\(h(n, m)\) を全て \(2\) で割った後に除原理の DP の逆となる DP をして連結性を失わせれば単純二部グラフの個数 \(f(n, m)\) が求まります。すなわち

\[f(n, m) = \frac{h(n,m)}{2} + \sum_{1 \leq i \lt n} \sum_{0 \leq j \leq m} \binom{n-1}{i-1} f(i, j) \frac{h(n-i,m-j)}{2}\]

という漸化式に基づいて、先の DP の逆向きの計算を行えばよいです。

以上より \(f(N, 0), \dots, f(N, L)\) を列挙することができました。計算量は \(\mathrm{O}(N^6)\) ですが定数倍に \(1/64\) がつくため十分高速に動作します。

以上よりこの問題を \(\mathrm{O}(N^6 + N^4 \log M)\) で解くことが出来ました。

余談 1 : 母関数による解釈

\(f(n, m)\) と \(g(n, m)\) の関係性については、2 変数母関数を利用して別の説明を与えることが出来ます。
頂点に関しては指数型母関数、辺に関しては通常型母関数を取る 2 変数母関数を考えます。\(F, G, H\) を次のように置きます。

\[F(x, y) = 1 + \sum_{n,m} \frac{x^n y^m}{n!} f(n, m)\]

\[G(x, y) = 1 + \sum_{n,m} \frac{x^n y^m}{n!} g(n, m)\]

\[H(x, y) = \sum_{n,m} \frac{x^n y^m}{n!} h(n, m)\]

実は除原理 DP は \(\log\) を計算する操作、その逆は \(\exp\) を計算する操作に対応していて、2 回の DP はそれぞれ

\[H = \log(G), F = \exp\left(\frac{H}{2} \right)\]

を計算していることになります。理由を簡潔に説明すると、\(H=\log(G)\) の方は

\[\exp(H)=G \to G\frac{\partial H}{\partial x} = \frac{\partial G}{\partial x}\]

という式の適当な次数の係数を比較すると前述の漸化式と同じ式が得られます。(逆も同様です)
2 つの式を合成することで、

\[F^2 = \exp \left(\frac{\log(G)}{2} \times 2 \right) = G\]

という想像以上に単純な \(F\) と \(G\) の関係式が得られます。この \(F^2 = G\) という式の組合せ的解釈を考えてみると、

• \(G =\) (\(g\) の数える対象の母関数)
  \(=\) (連結成分の一番若い番号の頂点を黒く塗ったものの母関数) \(\times\) (連結成分の一番若い番号の頂点を白く塗ったものの母関数)
  \(=\) \(F \times F\)

という解釈を得ることが出来ます。(この解釈に基づいた DP で \(G\) から \(F\) を計算することもおそらく可能です。)
また、このような \(G\) に対する \(F\) (すなわち定数項が \(1\) である平方根) を形式的冪級数の sqrt と呼び \(F = \sqrt{G}\) のように表します。

余談 2 : 別解

別解を簡単に紹介します。
想定解と同様 \(L := \lfloor N/2 \rfloor \lceil N/2 \rceil\) とします。詳細は略しますが、想定解と同様の DP によって、\(N\) を固定したときの答えの初め \(L+1\) 項 \(a(N,0), a(N, 1), \dots, a(N, L)\) を列挙できます。
また、\(N\) を固定した時、答えの母関数はある定数 \(C\) と \(L-1\) 次以下の多項式 \(P(x)\) を用いて

\[\sum_{m \geq 0} a(N, m) x^m = C + \frac{P(x)}{(1-x)(1-2x)\dots (1-Lx)}\]

と表せます。(想定解の議論、およびスターリング数 \(S(N,k)\) \((k \leq L)\) が \(0^M, 1^M, \dots, L^M\) の線形結合で表せることから示せます。) この事実から \(C\) の影響がない部分である \(a(N, 1), a(N, 2), \dots\) (\(m=1\) 始まりに注意) は \(L\) 次の線形漸化式によって表せる数列であることが言えます。よって、\(a(N,0),a(N,1)\dots,a(N,L)\) の値から \(C, P(x)\) を復元して \(\lbrack x^M \rbrack \frac{P(x)}{(1-x)(1-2x)\dots (1-Lx)}\) を Bostan-Mori 法で求めることで \(a(N, M)\) を求められます。(Bostan-Mori 法は ABC300 Ex の解説 を参考にしてみてください。) また、この事実がわかっていなくても、Berlekamp-Massey 法と呼ばれるアルゴリズムを利用すれば線形漸化性を実験的に確認して AC することが可能です。