[AtCoder] 第二回全国統一プログラミング王決定戦予選 B – Counting of Trees

問題

方針

一見難しそうに見えますが、\( 300 \) 点の問題なので解法は簡単であることが予想できます。

実現不可能な整数列

  • 頂点 \( 1 \) からの距離について

頂点 \( 1 \) からの距離が与えられるので、\( D_1 = 0 \) が必要です。

  • \( N – 1 \) 辺が存在する

\( N – 1 \) 辺存在することから、\( D_i \neq 0 \ ( i \neq 1)\) が必要です。つまり、距離が \( 0 \) となる頂点は頂点 \( 1 \) だけです。

  • 距離の連続性

距離が \( i \) である頂点の個数を \( d_i \) とします。\( d_i \neq 0 \) を満たす最大の \( i \) を \( j \) とします。このとき、\( d_i \neq 0 \ (1 \leq i \leq j – 1) \) を満たす必要があります。例えば、距離が \( 9 \) の頂点が存在するとき、\( 8 \) 以下の距離について、少なくとも一つ以上頂点が存在する必要があります。

距離の頻度に着目

距離が \( i \) である頂点の個数を \( d_i \) とします。また、\( D_1 = 0 \) であり、\( d_0 = 1 \) であるとします。距離 \( 1 \) から順に考えていきます。

距離 \( 1 \) までの木を考えると、接続される頂点は \( 1 \) なので、\( d_1 \) の値に依らず木は一意に定まります。次に、距離 \( 2 \) までの木を考えると、接続される頂点の候補は \( d_1 \) 個あるので、\( d_1^{d_2} \) 個の木が考えられます。同様にして距離 \( N – 1 \) まで考えると、求める木の個数は、

\[d_0^{d_1} \times d_1^{d_2} \times \cdots \times d_{N-2}^{d_{N-1}}\]

となります。また、計算過程で階乗の剰余を行う必要があります。

コード