yukicoder No.1302 Random Tree Score O(N+logp)

プリューファーコードというものを考えまふ. 

ja.wikipedia.org

 

木の各頂点の次数は, 対応するプリューファーコードにその頂点番号が現れる回数+1に等しいれふ.

プリューファーコードを次数列に対応させる試みとして, 次のような操作を考えまふ.

N 個の箱の中に白玉が1個ずつ入ってる状態から, 次の操作を N-2 回行う.

  •    箱を一つ選び, 白玉を1個入れる.

(箱同士・玉同士を区別することに注意)

すると, 次数の総積は次の値に一致しまふ.

  • 各箱から白玉を1個ずつ選び, 黒玉に取り換える方法の通り数

全ての次数列に対してこの値を求めるには, 次のような操作の通り数を考えれば良いれふ.

 

N 個の箱の中に白玉が1個ずつ入ってる状態から, 次の操作を N-2 回行う.

  •    箱を一つ選び, 白玉を1個入れる. または, まだ黒玉が入って無い箱を一つ選び, 黒玉を入れる.

操作後, まだ黒玉が入って無い箱すべてに対し, 最初から入ってた白玉を黒玉に取り換える.

x=0,1,2,...,N-2 に対し, N-2 回の操作のうち黒玉を x 回入れる方法は, 次のものを掛け合わせた数れふ.

  • N-2 回の操作から x 回を選ぶ通り数
  • N 個の箱から黒玉を入れる箱を重複なく選ぶ通り数
  • N 個の箱から白玉を入れる箱を重複を許して選ぶ通り数

適切に前計算をすれば O(N+logp) になりまふ.