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: <><

dp[i] を、条件を満たす順列のうち、末尾が i であるものの数とする。

最初は、長さ $1$ の順列だけなので次の状態である。

dp: {1}

$1$ 文字目は '<' である。
先頭に 0 を足してから、前から累積和を取る。

dp: {0, 1}

$2$ 文字目は '>' である。
末尾に 0 を足してから、後ろから累積和を取る。

dp: {1, 1, 0}

$3$ 文字目は '<' である。
先頭に 0 を足してから、前から累積和を取る。

dp: {0, 1, 2, 2}

全体の和を取る。

0 + 1 + 2 + 2 = 5

よって答えは $5$ である。

注意点

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

別解

特になし。