Gọi ~dp_{i,j}~ là số hoán vị độ dài ~i + 1~ thoả mãn điều kiện với ~i~ dấu đầu tiên trong xâu ~S~ và ~j~ là phần tử cuối cùng trong hoán vị.

Xét ~dp_{i,j}~. Ta biết cấu hình hiện tại là 1 hoán vị ~(P_1, P_2, \cdots, P_{i + 1})~ và ~P_{i + 1} = j~. Như vậy ~(P_1, P_2, \cdots, P_{i})~ là hoán vị của tập ~A = \{1, 2, \cdots, j - 1, j + 1, \cdots, i + 1\}~. Vì trong phạm vi bài toán, ta chỉ quan tâm đến quan hệ tương đối giữa các phần tử nên ta có thể dịch các phần tử lớn hơn ~j~ trong ~A~ mỗi phần tử xuống ~1~ đơn vị. Như vậy, tập ~A~ cũng tương đương như tập ~B = \{1, 2, \cdots, i\}~. Cụ thể:

• ~1~ trong tập ~A~ là ~1~ trong tập ~B~
• ~2~ trong tập ~A~ là ~2~ trong tập ~B~
• ...
• ~j - 1~ trong tập ~A~ là ~j - 1~ trong tập ~B~
• ~j + 1~ trong tập ~A~ là ~j~ trong tập ~B~
• ...
• ~i + 1~ trong tập ~A~ là ~i~ trong tập ~B~

Lúc này số cấu hình ~(P_1, P_2, \cdots, P_{i})~ cũng là số hoán vị thoả yêu cầu của tập ~B~ chỉ gồm ~i~ số nguyên dương đầu tiên. Như vậy:

• Nếu ~s_i~ là > thì ~dp_{i,j} = \sum_{k \geq j} dp_{i - 1,k}~ do các số lớn hơn ~j~ trong tập ~A~ tương đương với các số lớn hơn hoặc bằng ~j~ trong tập ~B~.
• Ngược lại thì ~dp_{i,j} = \sum_{k < j} dp_{i - 1,k}~ do các số bé hơn ~j~ trong tập ~A~ tương đương với các số bé hơn ~j~ trong tập ~B~.

Dùng mảng tổng tiền tố để tính nhanh ~\sum dp_{i - 1, k}~ trong ~O(1)~.

Độ phức tạp: ~O(N^2)~

Code mẫu:

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MOD = 1e9 + 7;
const int N = 3002;

int n;
ll f[N][N];
string s;

int main() {
    cin >> n;
    f[1][1] = 1;
    for (int i = 2; i <= n; ++i) {
        char ch;
        cin >> ch;
        for (int j = 1; j <= i; ++j) {
            if (ch == '<') {
                f[i][j] = f[i - 1][j - 1];
            } else {
                f[i][j] = (f[i - 1][i - 1] + MOD - f[i - 1][j - 1]) % MOD;
            }
        }
        for (int j = 1; j <= i; ++j)
            (f[i][j] += f[i][j - 1]) %= MOD;
    }
    cout << f[n][n] << "\n";
    return 0;
}