EDPC T - Permutation

考え方

ABCでいうと、F問題級。

入力例1のところにある $5$ つの順列を見てみる。

末尾が 4 のものは $2$ つある。
最後の 4 を削除すれば、最初 $3$ つの全ての並び順になる。

末尾が 3 のものは $2$ つある。
最後の 3 を削除して 4 を 3 に書き換えれば、最初 $3$ つの全ての並び順になる。

末尾が 2 のものは $1$ つある。
最後の 2 を削除して 4 を 3 に、3 を 2 にすれば、最初 $3$ つの並び順のうち末尾が 1 のものになる。

要するに、末尾が j であるものの個数は、以下で求められる。
最後が '<' である場合、$1$ つ少ない順列で末尾が j 未満であったものと同じ個数ある。
最後が '>' である場合、$1$ つ少ない順列で末尾が j 以上であったものと同じ個数ある。
よって、それらを累積和で高速処理すれば、動的計画法部分は簡単。

つまり、以下をやるだけである。

• 最初に、deque で {1} を用意しておく
• $s$ を前から $1$ 文字ずつ見て、以下を実行する
  • '<' の場合は、先頭に0をつけ足してから、前から累積和を取る
  • '>' の場合は、末尾に0をつけ足してから、後ろから累積和を取る

計算量は $O(N^2)$。

入力例1での動作

入力を受け取る。

n: 4
s: <><

長さごとに、条件を満たす順列を末尾の値で分類して数える。

長さ $1$ では順列は $1$ つだけである。

最初の条件は $<$ である。

新しい末尾が $j$ の順列は、それまでの末尾が $j$ 未満だった順列から作れる。
したがって、左からの累積和を使う。

長さ $2$ では次の状態になる。

{0, 1}

次の条件は $>$ である。

新しい末尾が $j$ の順列は、それまでの末尾が $j$ 以上だった順列から作れる。
今度は右からの累積和を使う。

長さ $2$ の状態 $\{0,1\}$ から求めると、次のようになる。

したがって、長さ $3$ の状態は次のようになる。

{1, 1, 0}

最後の条件は $<$ である。
再び左からの累積和を使う。

長さ $4$ の状態は次のようになる。

{0, 1, 2, 2}

全ての末尾について足すと、$0+1+2+2=5$ となる。
したがって、答えは $5$。

注意点

答えは $10^9+7$ で割った余りを要求されているので、剰余類環の考えに従って処理する。
足し算をするたびに結果を % 1000000007 する。

別解

特になし。