ラグランジュ補間を用いて、時間計算量 \(O(N^{6})\) で解くことができます。

まず、\(\mathrm{dp}[i][j][k]\) を、以下を満たす多項式と定義します。

• 任意の非負整数 \(a\) について、\([x^{a}]\mathrm{dp}[i][j][k]\) は、下記の場合の数と等しい。
  • \(N\) 頂点のうち、頂点 \(1\) と連結な頂点が \(i\) 個で、残りの \(N - i\) 個の頂点には辺がはっていない。また、\(1\) から一番遠い頂点の数が \(j\) 個で、\(1\) からの距離の偶奇が、\(1\) から一番遠い頂点との距離の偶奇と等しい頂点の数が \(k\) 個

答えは、 \(\mathrm{dp}[N][1][\frac{N}{2}] + \mathrm{dp}[N][2][\frac{N}{2}] + \cdots +\mathrm{dp}[N][\frac{N}{2}][\frac{N}{2}] \) です。

この dp の値を全て求めるには、以下の式の遷移を繰り返せば良いです。

\[\mathrm{dp}[i + a][a][i - k + a] += \mathrm{dp}[i][j][k]\times \dbinom{N - i}{a}\times (1 + x)^{\frac{a(a - 1)}{2}}\times((1 + x)^{j} - 1)^{a}\]

この式の計算をする回数は \(O(N^{4})\) 回ですが、多項式の計算をするため、実際の計算量は、雑な解析をすると、 \(\Theta(N^{8})\) などとなります。

ここで、ラグランジュ補間を使います。

ラグランジュ補間用いることで、\(n\) 次多項式 \(f(x)\) について、相異なる数 \(a_{1}, a_{2}, \dots , a_{n + 1}\) に対する \(f(a_{1}), f(a_{2}), \dots , f(a_{n + 1})\) の値がわかっていれば、 \(f(x)\) の全ての係数がわかります。

よって、上の DP の遷移を具体的に \(x = 1, 2, \dots, \frac{N(N -1)}{2} + 1\) に対して行い、答えに、これらの \(x\) を代入した値を求めた後、ラグランジュ補間で、答えの多項式を復元すれば良いです。

\(n\) 次多項式 \(f(x)\) の係数復元は時間計算量 \(O(n^{2})\) で行うことができるため、この問題では \(O(N^{4})\) で行うことができます。

よって、\(1 + \frac{N(N - 1)}{2}\) 回の dp がボトルネックとなって、全体の計算量 \(O(N^{6})\) で行うことができます。

空間計算量は \(O(N^{3})\) で、投稿現在、使用メモリの値が一番小さいです。

c++ 実装例 71 ms