この問題はグラフを K-彩色する方法の個数を数える問題です。
まず、 \(N\) が小さい場合の解法を簡単に説明します。

• wata さんのスライド にも詳しい説明があるのでそちらもご参照ください。

\(s(k)\) を「ちょうど \(K\) 種類使って頂点を塗る通り数」とすると答えは

\[\sum_{i=1}^N \binom{K}{i} s(i)\]

になるので、\(s(1), \dots, s(N)\) を列挙できればよいです。これは部分集合 DP で \(\mathrm{O}(N 3^N)\) で計算出来ます。(参考:ABC213-G 解説)

この DP は Subset Convolution と呼ばれるアルゴリズムを利用すると高速化することができます。Subset Convolution とは、部分集合を引数に持つ関数 \(f(S), g(S)\) が与えられたときに

\[(f \ast g)(S) = \sum_{T \subseteq S} f(T) g(S \setminus T)\]

を計算するアルゴリズムのことをいいます。これは愚直に計算すると \(\mathrm{O}(3^N)\) で、部分集合 DP の解法はこの畳み込みを \(N\) 回呼んでいます。

そして、この畳み込みは \(\mathrm{O}(N^2 2^N)\) に高速化できます。

• 説明は割愛します。日本語話者の方は hos さんによる記事 の Subset Convolution の項の記述が非常に分かりやすいのでそちらをお読みください。英語話者の方は adamant さんの CodeForces の記事をお読みください。

この畳み込みを用いると、 \(\mathrm{O}(N^3 2^N)\) で \(s(1), s(2), \dots, s(N)\) を列挙することができます。

そして、この畳み込みは \(\mathrm{O}(N^2 2^N)\) に計算量を落とすことができます。 \(F(S)\) を \(S\) が非空な独立集合ならば \(1\), それ以外ならば \(0\) を取る関数とします。\(F(S)\) を \(K\) 個畳み込んだものを \(f^K\) と表すと、答えは \(V\) を頂点集合全体として

\[\left(\sum_{i=1}^{\min(K, N)} \binom{K}{i} f^K\right)(V)\]

になります。ここで \(f^n\) の意味を考えると \(n=0\) および \(n \geq N\) について \(f^{n}(S)\) は常に \(0\) に等しいことが確認できるので、シグマの下限を \(0\), 上限を \(K\) にして

\[\left(\sum_{i=0}^K \binom{K}{i} f^K\right)(V)\]

としてもよいです。そして、 \(g(S)\) を \(S\) が(空でも良い)独立集合ならば \(1\) を返す関数とすると、上式は \(g^K(V)\) になります。(組み合わせ的な解釈でも導出できます。)

よって Subset Convolution の pow を求めればよく、これは実は Subset Convolution で各点積を求めてた部分で代わりに各点での \(K\) 乗の計算をすればよいです。\(N\) 次までの pow を計算するのは \(\mathrm{O}(N^2)\) や \(\mathrm{O}(N \log N)\) で計算できるので、全体の計算量は Subset Convolution と同じ \(\mathrm{O}(N^2 2^N)\) のまま計算できます。(hos さんの記事の後半部分に、似たような例に関する少し詳しい解説があります。)

次に \(M\) が小さい場合の解法を簡単に説明します。
辺の集合に関して包除原理を適用します。つまり、辺集合 \(E\) の部分集合 \(P\) について、「少なくとも \(e \in P\) である \(e\) について、\(e\) に隣接する頂点同士の色が一致している通り数」を計算して \((-1)^{|P|}\) の重みをつけて足し合わせます。すると次の式を得られます。

\[\sum_{P \subseteq E} (-1)^{|P|} K^{k(V, P)}\]

(ここで \(k(V, P)\) は頂点集合が \(\lbrace 1,2,\dots,N\rbrace\), 辺集合が \(P\) であるグラフの連結成分数。)

この式を利用すると、全探索で \(\mathrm{O}(N 2^M)\), あるいは辺の選び方で DFS + rollback Union-Find を利用して \(\mathrm{O}(2^M \log N)\) で答えを計算できます。

上式は次のように辺を \(1\) 本ずつ減らしていく DP としても解釈できます。グラフ \(G\) の K-彩色の通り数を \(F(G)\) とします。すると、\(G\) の辺 \(e\) を 1 つ取ってそれに注目すると、

\[F(G) = F(G - e) - F(G \setminus e)\]

という式が成り立ちます (ここで \(-\) は辺の削除, \(\setminus\) は辺の縮約) 。また、\(G\) に孤立点 \(v\) がある場合は

\[F(G) = K F(G - v)\]

という式が得られます。(\(-\) は頂点の削除)

さて、想定解の解説をすると、想定解はこの式を利用します。つまり、辺を何本か選んで、その辺を削除 or 縮約した場合のグラフの彩色数を再帰的に計算する方法を考えます。
具体的には、\(G\) の次数最小の頂点を 1 つ取り \(v\) とします。\(v\) の次数が \(0\) の場合は

\[F(G) = K F(G - v)\]

です。
\(v\) の次数が \(1\) の場合は、\(v\) に隣接する辺を \(e\) とすると、グラフ \(G' = (V \setminus \lbrace v \rbrace, E \setminus \lbrace e \rbrace)\) を用いて

\[F(G) = (K - 1) F(G')\]

になるのでこれも再帰的に計算できます。

次に、\(v\) の次数が \(2\) の場合を考えます。 \(v\) に隣接する辺を \(e_1, e_2\) とします。\(e_1, e_2\) について辺の縮約・削除 4 通りを考えます。順に

\[G_1 = (G-e_1)-e_2, G_2 = (G-e_1)\setminus e_2\]

\[G_3 = (G\setminus e_1)-e_2, G_4 = (G\setminus e_1) \setminus e_2\]

と呼びます。すると \(G_2\) と \(G_3\) は同型で、\(G_1\) は \(G_2\) に孤立点 \(v\) を追加したグラフです。よって

\[ \begin{aligned} &F(G) \\ &= F(G_1) - F(G_2) - F(G_3) + F(G_4) \\ &= (K - 2) F(G_2) + F(G_4) \end{aligned} \]

となり、辺の本数が \(2\) 本減ったグラフ \(2\) 個について再帰的に彩色の通り数を計算する式が立てられました。
一般化すると、\(v\) の次数に対して \(2^{\deg(v)} - \deg(v)\) 通りの subgraph の彩色数を考えればよいことがわかります。

これをを利用した解法と組み合わせます。\(v\) の次数が \(3\) 以上の場合は頂点数は \(\mathrm{ceil}(2M/3)\) で抑えられるので、Subset Convolution で \(\mathrm{O}(2^{2M/3} M^2)\) で計算できます。このとき、計算量は全体で \(\mathrm{O}(\max(2^{M/2} , M^2 2^{2M/3})) = \mathrm{O}(M^2 1.59^M)\) になります。

また、別解として、 Subset Convolution ではなく部分集合 DP を使う場合は \(v\) の次数が \(3\) の場合まで場合分けするのが最適で(\(5\) 通りの subgraph に場合分け)、このとき計算量は \(\mathrm{O}(\max(5^{M/3}, M 3^{M/2})) = \mathrm{O}(M 1.74^M)\) になります。指数の底は前述の解法よりも大きいですがこちらの解法も十分高速に動作します。

• 実装例 1, PyPy3, \(\mathrm{O}(M^2 1.59^M)\)
• 実装例 2, C++, \(\mathrm{O}(M 1.74^M)\)