Prerequisite

• bit DP (Dynamic Programming)

The transitions of the bit DP in this problem are very similar to that of what is explained in https://atcoder.jp/contests/abc213/tasks/abc213_g/editorial, so please refer to this.

• Kirchhoff’s theorem

We will just introduce the statement of the theorem, so please google “Kirchhoff’s theorem” if you want to learn the details.

Kirchhoff’s theorem

For an undirected graph \(G\) with \(N\) vertices and \(M\) edges, let us define the \(N \times N\) Laplacian matrix \(L\) by:

\(L_{i,j} := \begin{cases} \text{The degree of Vertex}i \ (i =j) \\ \text{The number of edges connecting Vertices }i\text{ and }j \times (-1) \ (\mathrm{otherwise}) \end{cases}\)

Then, the number of spanning trees in \(G\) is equal to any cofactor of \(L\).

Solution

We solve it by Kirchhoff’s theorem and bit DP.

Let \(V:=\{1,2,\ldots,N\}\) be the vertex set of \(G\). For \(S \subseteq V\), let us define \(f(S)\) and \(g_i(S)\) by:

• \(f(S):=\) The number of trees whose vertex set is \(S\subseteq V\)
• \(g_i(S):=\) The number of forests whose vertex set is \(S\subseteq V\) and containing \(i\) edges

Then, the answer for \(K=i\) can be expressed as \(\frac{g_i(V)i!}{m^i}\). Thus, it is sufficient to enumerate \(g_1(V),g_2(V),\ldots,g_{N-1}(V)\).

\(f(S)\) can be found by Kirchhoff’s theorem in a total of \(\mathrm{Ο}(N^3 2^N)\) time.

\(g_i(S)\) can be solved in the same way as ABC213-G. By taking arbitrarily fixed vertex (let us call it \(v\)) contained in \(S\), then the connected component containing \(v\) forms a tree, so the following relation holds:

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

By this equation, we can find \(g_i(S)\) in the increasing order of \(i\) in a total of \(\mathrm{Ο}(N 3^N)\) using the algorithm of iterating through the subsets.

Therefore, the problem has been solved in a total of \(\mathrm{Ο}(N^3 2^N + N 3^N)\) time.