1/21 PKU

2775 The Number of the Same BST

ある配列について、先頭の要素から順番に読み込んで二分探索木を構築する。二分探索木に要素を付け足すときには、すでにある構造を壊さない。左の子のキーは自分のキー以下で、右の子のキーは自分のキーより大きい。この条件下で、与えられた配列と同じ二分探索木を構築する配列の個数を9901で割った余りを求めよ。

ある配列について、先頭の要素が一番根っこに来る。これは変えられない。左に来る要素、右に来る要素（の順番）も自ずと決まってくる。でも、左右に来る要素の順番が合っていれば、それをどう混ぜても構わない。これはC(左+右,左)で求まる。あとは左、右に対して再帰的に答えを求めて掛けあわせる。