Submission #35802959

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;
using ll = long long;

struct mint {
    int n;
    mint() : n(0) { ; }
    mint(ll m) {
        if (m < 0 || MOD <= m) {
            m %= MOD;

            if (m < 0)
                m += MOD;
        }

        n = m;
    }
    operator int() {
        return n;
    }
};
bool operator==(mint a, mint b) {
    return a.n == b.n;
}
mint operator+=(mint &a, mint b) {
    a.n += b.n;

    if (a.n >= MOD)
        a.n -= MOD;

    return a;
}
mint operator-=(mint &a, mint b) {
    a.n -= b.n;

    if (a.n < 0)
        a.n += MOD;

    return a;
}
mint operator*=(mint &a, mint b) {
    a.n = ((ll)a.n * b.n) % MOD;
    return a;
}
mint operator+(mint a, mint b) {
    return a += b;
}
mint operator-(mint a, mint b) {
    return a -= b;
}
mint operator*(mint a, mint b) {
    return a *= b;
}
template<typename T>
mint operator^(mint a, T n) {
    if (n == 0)
        return mint(1);

    mint res = (a * a) ^ (n / 2);

    if (n % 2)
        res = res * a;

    return res;
}
ll inv(ll a, ll p) {
    return (a == 1 ? 1 : (1 - p * inv(p % a, a)) / a + p);
}
mint operator/(mint a, mint b) {
    return a * mint(inv(b, MOD));
}
mint operator/=(mint &a, mint b) {
    a = a / b;
    return a;
}

int main() {
    cin.tie(NULL)->ios_base::sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> v(n);

    for (auto &x : v)
        cin >> x;

    auto f = vector(n + 1, vector(n + 1, mint(1)));

    for (int len = 2; len < n; ++len) {
        for (int l = 1, r = l + len - 1; r < n; ++l, ++r) {
            f[l][r] = 0;

            for (int k = l + 1; k <= r + 1; ++k) {
                if (k > r || v[k] > v[l]) {
                    f[l][r] += f[l + 1][k - 1] * f[k][r];
                }
            }
        }
    }

    cout << f[1][n - 1] << endl;
    return 0;
}

Submission Info

Judge Result