https://kyopro.hateblo.jp/entry/2019/01/28/184751

問題. Permutation

各文字が '<' か '>' からなる長さ $n - 1$ の文字列 $s$ が与えられる． $N = \{1, 2, \ldots, n\}$ 上の順列 $\pi$ で次の条件を満たすものが何通りあるか求めよ．
　・ $s_i$ が '<' ならば $\pi_{i} < \pi_{i + 1}$
　・ $s_i$ が '>' ならば $\pi_{i} > \pi_{i + 1}$
制約： $2 \le n \le 3,000$

解法

解法が思いつかなかったので kmjpさんのブログを参考にしました．
　Educational DP Contest : T - Permutation - kmjp's blog

順列を先頭から決めていくことを考えます．初めから $i - 1$ 番目までの列 $\pi_1, \ldots, \pi_{i-1}$ が決まっており $i$ 番目の要素 $\pi_i$ を決めます．また， $X \subseteq N$ をまだ選ばれていない要素の集合とします．このとき， $s_{i-1}$ が '<' ならば $\pi_i$ は $X$ の中で $\pi_{i - 1}$ よりも大きいものしか選ぶことができません．もし， $\pi_{i - 1}$ が 5 で $X = \{1, 3, 6, 8\}$ のとき選べるのは $6, 8$ となります．また， $X' = \{1, 2, 7, 9\}$ のとき選べるのは $7, 9$ となります．ここで， $\pi_i$ 以降での順列の数は $X$ と $X'$ で等しくなります．この2つの共通点は $X$ と $X'$ の中で $\pi_{i-1}$ が何番目に小さいかが等しいということです．したがって，dp[i][j] を $1$ から $i$ 番目までを決めたときのまだ選ばれていない $N$ の要素の中で $i$ 番目の要素が $j$ 番目に小さい順列の数　として動的計画法を行います．遷移は，
　・ $s_{i-1} =$ '<' の場合：dp[i][j] = dp[i - 1][j - 1] + ... + dp[i - 1][1]
　・ $s_{i-1} =$ '>' の場合：dp[i][j] = dp[i - 1][j + 1] + ... + dp[i - 1][n - i + 2]
となります．ここで，各場合での右辺の和は累積和で $i$ を決める前に前処理を $O(n)$ 時間でを行い，各 $j$ に対して $O(1)$ 時間で部分和を求めることができます．よって全体の計算時間は $O(n^2)$ となります．

計算時間： $O(n^2)$

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    constexpr ll MOD = 1e9 + 7;

    int n;
    string s;
    cin >> n >> s;

    vector<vector<ll>> dp(2, vector<ll>(n + 1));
    auto &cur = dp[0], &nxt = dp[1];

    for (int i = 1; i <= n; ++i) cur[i] = 1;
    for (int i = 2; i <= n; ++i) {
        for (int j = 1; j <= n - i + 2; ++j) {
            cur[j] += cur[j - 1];
            nxt[j] = 0;
        }

        for (int j = 1; j <= n - i + 1; ++j) {
            if (s[i - 2] == '<') (nxt[j] += (cur[j] - cur[0] + MOD)) %= MOD;
            else (nxt[j] += (cur[n - i + 2] - cur[j] + MOD)) %= MOD;
        }
        swap(cur, nxt);
    }

    cout << cur[1] << endl;

    return 0;
}

　
上のソースコードをまとめるとほんの少し高速になります．

修正したソースコードを表示

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

int main() {
    cin.tie(0); ios::sync_with_stdio(false);

    constexpr ll MOD = 1e9 + 7;

    int n;
    string s;
    cin >> n >> s;

    vector<int> cur(n + 1, 1), nxt(n + 1);
    cur[0] = 0;

    for (int i = 2; i <= n; ++i) {
        if (s[i - 2] == '<') {
            for (int j = 1, sum = 0; j <= n - i + 1; ++j)
                nxt[j] = ((sum += cur[j]) %= MOD);
        }
        else {
            for (int j = n - i + 1, sum = 0; 1 <= j; --j)
                nxt[j] = ((sum += cur[j + 1]) %= MOD);
        }
        swap(cur, nxt);
    }

    cout << cur[1] << endl;

    return 0;
}

列挙木を書いて眺めてもどの状態をまとめれば良いのか思いつかなかったので悔しい．
典型らしいのでものにしたいけど，どうメタ的に捉えればいいのか分からない．