正の整数の列 b 1 , … , b n b_1, \dots, b_n b 1 , … , b n に対して、g ( b ) i g(b)_i g ( b ) i を「i i i より左にあって b j < b i b_j < b_i b j < b i を満たす j j j のうち最大のもの(なければ 0 0 0 )」と定めます。ある b b b によって y = g ( b ) y = g(b) y = g ( b ) と書ける列 y y y を「復元可能」と呼びます。
長さ n n n の列 x x x が与えられます。x x x のいくつかの要素は − 1 -1 − 1 です。− 1 -1 − 1 をそれぞれ 0 0 0 以上 n n n 以下の整数に置き換えて x x x を復元可能にする方法の数を、10 9 + 7 10^9 + 7 1 0 9 + 7 で割った余りで求めてください(n n n の総和 ≤ 5000 \le 5000 ≤ 5000 )。
b b b の Cartesian Tree を考えます。最小値を根にし、頂点は中間順に添字 1 , … , n 1, \dots, n 1 , … , n で並べます。値が等しい要素は、後ろにあるほうを小さい とみなします。g g g の定義が真の不等号 b j < b i b_j < b_i b j < b i なので、こうすると「b j < b i b_j < b_i b j < b i 」と「j j j のほうが小さい(j < i j < i j < i のとき)」が一致します。
このとき、i i i の左部分木はちょうど区間 [ g i + 1 , i − 1 ] [g_i + 1, i - 1] [ g i + 1 , i − 1 ] になります 。i i i の左部分木は「i i i から左へ、i i i より大きい要素が続く範囲」で、その左端の外側が i i i より左で最も近い小さい要素、つまり g i g_i g i だからです。
g g g とツリーの形は一対一に対応します。スタックを使った Cartesian Tree の作り方で考えると分かりやすいです。
根から右の子だけをたどった道(以下、右端の道)をスタックで持つ
i i i を追加するときは、b i b_i b i より大きい要素をスタックから pop する。pop した部分が i i i の左部分木になり、i i i は残ったスタックの一番上の右の子になる。最後に i i i を push する
pop し終わったときのスタックの一番上が、ちょうど g i g_i g i です(空なら 0 0 0 )。そのため、各ステップで何個 pop するかは g g g から決まり、ツリーの形も g g g から決まります。逆に、どんな形のツリーにも、それを作る b b b が存在します(例えば、根からの深さをそのまま b b b にすればよいです)。
まとめると、復元可能な y y y と、n n n 頂点の二分木の形は一対一に対応します 。全部が − 1 -1 − 1 のときの答えは Catalan 数 C n C_n C n で、サンプル 3 の 132 = C 6 132 = C_6 132 = C 6 と一致します。
例えば g = [ 0 , 1 , 2 , 1 , 0 , 0 , 6 ] g = [0, 1, 2, 1, 0, 0, 6] g = [ 0 , 1 , 2 , 1 , 0 , 0 , 6 ] に対応するツリーの親は、[ 5 , 4 , 2 , 1 , 6 , − , 6 ] [5, 4, 2, 1, 6, -, 6] [ 5 , 4 , 2 , 1 , 6 , − , 6 ] です(6 が根)。4 の左部分木が [ g 4 + 1 , 3 ] = [ 2 , 3 ] [g_4 + 1, 3] = [2, 3] [ g 4 + 1 , 3 ] = [ 2 , 3 ] になっていることなどが確かめられます。
この対応を使うと、問題は次のように言い換えられます。
頂点 1 , … , n 1, \dots, n 1 , … , n を中間順に並べた二分木のうち、x i ≠ − 1 x_i \ne -1 x i = − 1 であるすべての i i i について「i i i の左部分木がちょうど [ x i + 1 , i − 1 ] [x_i + 1, i - 1] [ x i + 1 , i − 1 ] である」ものを数える
x i ≥ i x_i \ge i x i ≥ i のときは、そのような左部分木はありえないので答えは 0 0 0 です。
x i ≠ − 1 x_i \ne -1 x i = − 1 のとき、i i i の左部分木 [ x i + 1 , i − 1 ] [x_i + 1, i - 1] [ x i + 1 , i − 1 ] は、それだけで閉じた部分木です。この部分の形は、外側の形とは無関係に選べます。また外側から見ると、左部分木ごと i i i に潰してしまえば、i i i は「左の子を持たない頂点」 として扱えます。
そこで、左から順に頂点を見ながら、次のように列を潰していきます。
x i = − 1 x_i = -1 x i = − 1 のとき:i i i を「自由な頂点」として列の末尾に加える
x i ≠ − 1 x_i \ne -1 x i = − 1 のとき:列の中から x i + 1 x_i + 1 x i + 1 以降に始まる要素をすべて取り出す。それらが i i i の左部分木になるので、その形の数を答えに掛ける。そのあと、x i + 1 x_i + 1 x i + 1 から i i i までをまとめて「左の子を持たない頂点」1 個として末尾に加える
列の各要素が元の列のどこから始まるかを記録しておきます。取り出す範囲の先頭が x i + 1 x_i + 1 x i + 1 から始まる要素になっていないとき、つまり x i + 1 x_i + 1 x i + 1 がすでに潰された要素の内側にあるときは、答えは 0 0 0 です。i i i の左部分木の境界が、ほかの頂点の左部分木と交差してしまうからです。
最後に残った列全体の形の数も掛ければ、答えになります。
あとは「列の各要素が、自由な頂点か、左の子を持たない頂点か」が決まっているときに、中間順がその列になる二分木の数を求めればよいです。
Cartesian Tree の作り方と同じく、右端の道をスタックで持ちながら頂点を 1 個ずつ追加することにします。スタックの高さが h h h のとき、次の頂点を追加する方法は次のとおりです。
自由な頂点:0 0 0 個以上 h h h 個以下を pop してから push するので、新しい高さは 1 1 1 以上 h + 1 h + 1 h + 1 以下
左の子を持たない頂点:pop しないで push するので、新しい高さは h + 1 h + 1 h + 1
pop の仕方とツリーの形は一対一に対応するので、d p [ h ] \mathrm{dp}[h] dp [ h ] を「スタックの高さが h h h になる方法の数」とする DP で数えられます。自由な頂点の遷移は
d p ′ [ h ′ ] = ∑ h ≥ h ′ − 1 d p [ h ] \mathrm{dp}'[h'] = \sum_{h \ge h' - 1} \mathrm{dp}[h] dp ′ [ h ′ ] = h ≥ h ′ − 1 ∑ dp [ h ]
なので、後ろからの累積和 で O ( 長さ ) O(\text{長さ}) O ( 長さ ) で計算できます。答えは最後の d p \mathrm{dp} dp の総和です。
各頂点はちょうど 1 回だけ、どれか 1 つの列の DP に参加します。長さ m m m の列の DP は O ( m 2 ) O(m^2) O ( m 2 ) なので、全体で O ( n 2 ) O(n^2) O ( n 2 ) です。
Python
from bisect import bisect_left
from itertools import accumulate
s = list ( accumulate ( reversed ( dp )))
dp = [ 0 ] + [ v % MOD for v in s ]
for i in range ( 1 , n + 1 ):
k = bisect_left ( starts , l )
if l < i and (k == len ( starts ) or starts[k] != l):
ans = ans * count ( flags [ k: ]) % MOD
return ans * count ( flags ) % MOD
x = list ( map ( int , input () . split ()))
starts は列の各要素が元の列のどこから始まるか、flags はその要素が左の子を持たない頂点かどうかです。starts は昇順なので、x i + 1 x_i + 1 x i + 1 から始まる要素を bisect_left で探しています。
count が二分木の数え上げの DP です。dp[h] はスタックの高さが h になる方法の数で、左の子を持たない頂点では高さが 1 増えるだけなので、先頭に 0 を足してずらします。自由な頂点では、後ろからの累積和をとってから先頭に 0 を足します。