問題文中で与えられた \(M\) を、以下では \(K\) と表します。

グラフ \(G\) に対して、その連結成分数を \(C(G)\) と表します。

「辺重みが \(1\) 以上 \(K\) 以下の整数である完全グラフ \(G\) 」全体がなす集合を \(S_K\) と表します。

\(G\in S_K\) に対して、重みが \(k\) より大きな辺を削除したグラフを \(G_k\) とします。

\(G\in S_K\) の最小全域木の重みを考えます。クラスカル法を考えると、重み \(k\) の辺が最小全域木に使われる回数は \(C(G_{k-1})-C(G_k)\) です。\(C(G_0)=N\) であることと、\(k\geq K\) のとき \(C(G_k)=1\) であることに注意すると、最小全域木の重みは

\(\displaystyle \sum_{k\geq 1}k(C(G_{k-1})-C(G_k))\\ = N-K+\sum_{k=1}^{K-1}C(G_k)\)

となります。よって求める値は

\(\displaystyle \sum_{G\in S_K}\left(N-K+\sum_{k=1}^{K-1}C(G_k)\right)\\ =(N-K)K^{\frac{N(N-1)}{2}}+\sum_{k=1}^{K-1}\sum_{G\in S_K}C(G_k)\)

です。各 \(k\) での\(\sum_{G\in S_K}C(G_k)\)、すなわち「頂点ラベル付き \(N\) 頂点完全グラフであって、辺重みが\(1\) 以上 \(K\) 以下の整数であるもの全てについての、重みが \(k\) より大きな辺を削除したときの連結成分数の和」が求まればよいです。

EGF(exponential generating function) を考えます。

「頂点ラベル付き \(N\) 頂点 \(M\) 辺単純グラフ」の個数を \(c_{N,M}\) とし、そのEGF を \(f(X; Y):=\sum_{n,m\geq 0}c_{n,m}Y^m\frac{X^n}{n!}=\sum_{n\geq 0} (1+Y)^{\frac{n(n-1)}{2}}\frac{X^n}{n!}\) とします。一般に、ある性質を満たす頂点ラベル付き単純連結グラフのEGFのexpは、その性質を満たす頂点ラベル付き単純グラフ(連結とは限らない)のEGFになります。よって、「頂点ラベル付き \(N\) 頂点 \(M\) 辺単純連結グラフ」のEGFは \(g:=\log(f)\) となります。

同様に、一般に、ある性質を満たす頂点ラベル付き単純連結グラフのEGFが \(F\) であるとき、その性質を満たす頂点ラベル付き連結グラフで、連結成分数が \(c\) であるものの EGF は、\(\frac{F^c}{c!}\) になります。このことから、「頂点ラベル付き \(N\) 頂点 \(M\) 辺単純グラフ全てを渡る連結成分数の和」のEGFは \(\displaystyle h:=\sum_{c\geq 1} c\frac{g^c}{c!}=g\exp(g)=f\log(f)\) となります。\(a_{n,m}\) を \(h(X;Y)=\sum_{n,m\geq 0}a_{n,m}Y^m\frac{X^n}{n!}\) とおきます。

存在している辺には \(1\) 以上 \(k\) 以下の整数を、存在していない辺には \(k\) より大きく \(K\) 以下の整数を割り当てることを考えることで「頂点ラベル付き \(N\) 頂点完全グラフであって、辺重みが\(1\) 以上 \(K\) 以下の整数であるもの全てについての、重みが \(k\) より大きな辺を削除したときの連結成分数の和」は

\(\displaystyle \sum_{m\geq 0} a_{N,m}k^m(K-k)^{\frac{N(N-1)}{2}-m}\\ =(K-k)^{\frac{N(N-1)}{2}}\sum_{m\geq 0} a_{N,m}\left(\frac{k}{K-k}\right)^m\\ =(K-k)^{\frac{N(N-1)}{2}}N![X^N]h\left(X;\frac{k}{K-k}\right)\)

となります。

各 \(k\) について \([X^N]h(X;\frac{k}{K-k})\) の計算は \(O(N\log N)\) でできることから、\(O(KN\log N)\) でこの問題を解くことができました。

一般に \(\log(F)=\int \frac{F'}{F}\) が成り立つため、これらの計算を \(O(KN\log N)\) で行うために必要なFPSライブラリは乗除算のみです。また、全てのFPSの計算をナイーブに行うとしても \(O(KN^2)\) 時間となります。