Editorial for Atcoder Educational DP Contest T - Permutation


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

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;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.