正の整数の列 b1,…,bn に対して、g(b)i を「i より左にあって bj<bi を満たす j のうち最大のもの(なければ 0)」と定めます。ある b によって y=g(b) と書ける列 y を「復元可能」と呼びます。
長さ n の列 x が与えられます。x のいくつかの要素は −1 です。−1 をそれぞれ 0 以上 n 以下の整数に置き換えて x を復元可能にする方法の数を、109+7 で割った余りで求めてください(n の総和 ≤5000)。
b の Cartesian Tree を考えます。最小値を根にし、頂点は中間順に添字 1,…,n で並べます。値が等しい要素は、後ろにあるほうを小さいとみなします。g の定義が真の不等号 bj<bi なので、こうすると「bj<bi」と「j のほうが小さい(j<i のとき)」が一致します。
このとき、i の左部分木はちょうど区間 [gi+1,i−1] になります。i の左部分木は「i から左へ、i より大きい要素が続く範囲」で、その左端の外側が i より左で最も近い小さい要素、つまり gi だからです。
g とツリーの形は一対一に対応します。スタックを使った Cartesian Tree の作り方で考えると分かりやすいです。
- 根から右の子だけをたどった道(以下、右端の道)をスタックで持つ
- i を追加するときは、bi より大きい要素をスタックから pop する。pop した部分が i の左部分木になり、i は残ったスタックの一番上の右の子になる。最後に i を push する
pop し終わったときのスタックの一番上が、ちょうど gi です(空なら 0)。そのため、各ステップで何個 pop するかは g から決まり、ツリーの形も g から決まります。逆に、どんな形のツリーにも、それを作る b が存在します(例えば、根からの深さをそのまま b にすればよいです)。
まとめると、復元可能な y と、n 頂点の二分木の形は一対一に対応します。全部が −1 のときの答えは Catalan 数 Cn で、サンプル 3 の 132=C6 と一致します。
例えば g=[0,1,2,1,0,0,6] に対応するツリーの親は、[5,4,2,1,6,−,6] です(6 が根)。4 の左部分木が [g4+1,3]=[2,3] になっていることなどが確かめられます。
この対応を使うと、問題は次のように言い換えられます。
頂点 1,…,n を中間順に並べた二分木のうち、xi=−1 であるすべての i について「i の左部分木がちょうど [xi+1,i−1] である」ものを数える
xi≥i のときは、そのような左部分木はありえないので答えは 0 です。
xi=−1 のとき、i の左部分木 [xi+1,i−1] は、それだけで閉じた部分木です。この部分の形は、外側の形とは無関係に選べます。また外側から見ると、左部分木ごと i に潰してしまえば、i は「左の子を持たない頂点」 として扱えます。
そこで、左から順に頂点を見ながら、次のように列を潰していきます。
- xi=−1 のとき:i を「自由な頂点」として列の末尾に加える
- xi=−1 のとき:列の中から xi+1 以降に始まる要素をすべて取り出す。それらが i の左部分木になるので、その形の数を答えに掛ける。そのあと、xi+1 から i までをまとめて「左の子を持たない頂点」1 個として末尾に加える
列の各要素が元の列のどこから始まるかを記録しておきます。取り出す範囲の先頭が xi+1 から始まる要素になっていないとき、つまり xi+1 がすでに潰された要素の内側にあるときは、答えは 0 です。i の左部分木の境界が、ほかの頂点の左部分木と交差してしまうからです。
最後に残った列全体の形の数も掛ければ、答えになります。
あとは「列の各要素が、自由な頂点か、左の子を持たない頂点か」が決まっているときに、中間順がその列になる二分木の数を求めればよいです。
Cartesian Tree の作り方と同じく、右端の道をスタックで持ちながら頂点を 1 個ずつ追加することにします。スタックの高さが h のとき、次の頂点を追加する方法は次のとおりです。
- 自由な頂点:0 個以上 h 個以下を pop してから push するので、新しい高さは 1 以上 h+1 以下
- 左の子を持たない頂点:pop しないで push するので、新しい高さは h+1
pop の仕方とツリーの形は一対一に対応するので、dp[h] を「スタックの高さが h になる方法の数」とする DP で数えられます。自由な頂点の遷移は
dp′[h′]=h≥h′−1∑dp[h]
なので、後ろからの累積和で O(長さ) で計算できます。答えは最後の dp の総和です。
各頂点はちょうど 1 回だけ、どれか 1 つの列の DP に参加します。長さ m の列の DP は O(m2) なので、全体で O(n2) です。
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 は昇順なので、xi+1 から始まる要素を bisect_left で探しています。
count が二分木の数え上げの DP です。dp[h] はスタックの高さが h になる方法の数で、左の子を持たない頂点では高さが 1 増えるだけなので、先頭に 0 を足してずらします。自由な頂点では、後ろからの累積和をとってから先頭に 0 を足します。