Submission #35802015

---

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

    auto f = vector(n, vector(n, mint(-1)));
    auto h = vector(n, vector(n, mint(0)));
    vector<vector<int>> rp(n);
    auto pos = vector(n, vector(n, 0));

    for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
            if (v[j] > v[i])
                rp[i].push_back(j);
        }
    }

    function<mint(int, int)> dfs = [&](int l, int r) {
        if (l > r)
            return f[l][r] = mint(0);

        if (l == r)
            return f[l][r] = mint(1);

        if (f[l][r] != mint(-1))
            return f[l][r];

        mint res = 0;

        for (int i = l + 1; i <= r; ++i) {
            mint now = i == l + 1 ? mint(1) : h[l][i];

            if (!now)
                continue;

            for (auto &j = pos[l][i]; j < rp[i].size() && rp[i][j] <= r; ++j) {
                h[l][rp[i][j]] += now * dfs(i, rp[i][j] - 1);
            }

            res += now * dfs(i, r);
        }

        return f[l][r] = res;
    };

    cout << dfs(0, n - 1) << endl;

    return 0;
}

Submission Info

Compile Error

./Main.cpp: In lambda function:
./Main.cpp:121:41: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  121 |             for (auto &j = pos[l][i]; j < rp[i].size() && rp[i][j] <= r; ++j) {
      |                                       ~~^~~~~~~~~~~~~~

Judge Result