前提知識

• bit DP

今回と似た遷移のbit DP が https://atcoder.jp/contests/abc213/tasks/abc213_g/editorial で詳しく解説されているので、そちらを参照してください。

• 行列木定理

以下では定理の主張のみを述べるので、証明などを知りたい方は行列木定理で調べてみてください。

行列木定理

\(N\) 頂点 \(M\) 辺の無向グラフ \(G\) に対し、\(N\times N\) のラプラシアン行列 \(L\) を以下で定義する。

\(L_{i,j} := \begin{cases} 頂点 i の次数 \ (i =j) \\ 頂点 i と頂点 j を結ぶ辺の本数 \times (-1) \ (\mathrm{otherwise}) \end{cases}\)

このとき、 \(G\) の全域木の個数は \(L\) の任意の余因子に等しい。

解法

行列木定理と bit dp により解きます。

以下では \(G\) の頂点集合を \(V:=\{1,2,\ldots,N\}\) とします。\(S \subseteq V\) を満たす \(S\) に対し、\(f(S),g_i(S)\) を以下で定めます。

• \(f(S):=S\subseteq V\) を頂点集合とする木の個数
• \(g_i(S):=S\subseteq V\) を頂点集合とする \(i\) 辺の森の個数

このとき、 \(K=i\) の場合の答えは \(\frac{g_i(V)i!}{m^i}\) と表すことができます。よって、\(g_1(V),g_2(V),\ldots,g_{N-1}(V)\) が列挙できれば良いです。

\(f(S)\)は、行列木定理により \(\mathrm{Ο}(N^3 2^N)\) で求めることができます。

\(g_i(S)\) は、ABC213-G と同様の方法で求められます。 \(S\) に含まれる頂点を任意に一つ固定すると（これを \(v\) とします）、\(v\) の連結成分は木を成しているので、以下の関係式が成立します。

\[g_i(S) = \sum_{v \in T \subset S} f(T)g_{i - (|T| - 1)}(S \setminus T) \]

この式に従い、部分集合を列挙するアルゴリズムを用い \(g_i(S)\) を昇順に計算することで、 \(g_i(S)\) は \(\mathrm{Ο}(N 3^N)\) で求められます。

以上よりこの問題を \(\mathrm{Ο}(N^3 2^N + N 3^N)\) で解くことができました。