作問：kuronosu1024

元の問題文

整数 $N$ が与えられます。
$N$ 個の頂点からなる互いに異なる（ラベルなし、根なし）木の総数を $X$ とします。 $X$ を$998244353$ で割った余りを求めてください。

想定エスパー法

$N$ に対して解の大きさが指数関数的に増加していることより、組み合わせ論的な数と予想できます。
また、$N < 4$ での値がかなり小さいことより対称性が強いものに焦点を当てると、後は気合で木の個数であることをエスパーします。

解説

分割数DPの要領で解くことができます。（FPSを使えば $N$ 倍高速ですが、ここでは解説しません）

1) 根付き木の数を数える

まず、$N$ 頂点の根付き木の総数について考えます

根に部分木を追加していくことを考えると、$dp[i]$ を $i$ 頂点の根付き木の総数と定義して愚直的な遷移を次のように考えられます

・ $A \in P_i$ について、（ $P_i$ は自然数 $i$ の分割の全体集合） $B[j]$ を $A$ に含まれる $j$ の個数として、

これで遷移はできるにはできますが、とりうる $A$ の種類数( $=|P_i|$ )は非常に大きな数になるので工夫する必要があります。

（分割とは 例）

例えば $i=5$ において、頂点数 $5$ の根付き木の作り方は次の $5$ 通りに分けられます

• 根に、大きさがそれぞれ $\{1,1,1,1\}$である計4つの木をつなげる
• 根に、大きさがそれぞれ $\{2,1,1\}$である計3つの木をつなげる
• 以下同様に、 $\{2,2\}, \{3,1\}, \{4\}$

この $\{1,1,1,1\}$ や $\{3,1\}$ といった集合を $4$ の分割といいます

（例終わり）

$dp_1[i][j]$ を、$i$ 頂点の根付き木の総数であって、根につながる部分木の大きさが全て $j$ 頂点以下であるものの総数と定義します。($dp[i] = dp_1[i][i-1]$)
$A$ のうち最も大きい数 $k$ を含まれる $B[k]$ 個全て削除したものを $A'$ とし、それに対応する $B$ を $B'$ として分けて考えると

$k$ , $B[k]$ が等しいもの同士をまとめると、（この時、$P'_i = (P_i のうちすべての要素が k-1 以下であるもの)$ とすると $A' \in P'_{i-kB[k]}$ が成り立つので）まとめた総和は

さらに、同じ $k$ についてもまとめて

この総和は $dp_1[i+1][k]-dp_1[i+1][k-1]$ に等しく、$dp[i+1]$ を求めるには、取りうる $k, B[k]$ について上式を求めればよく、その取りうる $k, B[k]$ というのは $O(N \log N)$ 種類で済みます。
また、2項係数も隣同士であるため $dp_1[i-kx+1][k-1] \cdot\binom{dp[k] +x - 1}{x}$ も適切に実装すればそれぞれ $O(1)$ で計算できます。

よって、 $O(N^2 \log N)$ で $dp[N]$ を求めることができ、今回の制約でこれは十分高速です。

2) 根なし木の数を数える

根なし木は根となる頂点を区別しないため、求めた値から重複分を減らす必要があります。重複分を数えるために木の重心を考えます。（根と重心が一致するもののみ数えることで重複なく根なし木の数を数えることができます。）

$N$ が奇数の時

このとき木の重心は常に $1$ 個 です。木の重心につながる部分木の大きさは常に $N/2$ 以下であるので、$dp_1[N][(N-1)/2]$ がそのまま答えになります。

$N$ が偶数の時

このとき木の重心は常に $1$ 個か $2$ 個で、$1$ 個の時は $N$ が奇数の時と同様に求められます (ただし、 $N/2$ の部分木があると重心が2個になってしまうので、代わりに $N/2 -1$ とする必要があります)。

$2$ 個の時は、その間の辺で分割したときちょうど $N/2$ 頂点の二つの木に分けられるので、そのような木は $\binom{dp[N/2]+1}{2}$ だけ存在します。

以上より、適切な前計算で必要なDPテーブルを $O(N^2 \log N)$ で求めることができるため、この問題にACすることができます。