题意

你拿到了一个神秘的字符串，这个字符串的长度为 $nn$ ，里面只有 $0,1,20,1,2$ 三种数。但是你意识到了事情并不简单，这个字符串实际上隐藏的是一个长度为 $n+1n\; +\; 1$ 的排列。我们将字符串和排列的下标从$11$开始标号，如果 $s[i]=1s[i]\; =\; 1$，那么说明排列 $aa$ 的 $a_i\le a_{i+1}a\_i\; \backslash le\; a\_\{i\; +\; 1\}$；如果 $s[i]=2s[i]\; =\; 2$ ，那么说明 $a_i\ge a_{i+1}a\_i\; \backslash ge\; a\_\{i\; +\; 1\}$；如果 $s[i]=0s[i]\; =\; 0$，那么说明 $a_{i}a\_i$ 和 $a_{i+1}a\_\{i\; +\; 1\}$ 的关系任意 现在你需要求出有多少种不同的排列满足条件，输出在模998244353意义下的答案

数据范围： $1\le n\le 5e31\; \backslash leq\; n\; \backslash leq\; 5e3$

题解

状态设置：

对于一个 $nn$ 位的排序，我们想要在第 $n+1n+1$ 位插入一个数 $jj$ 使得其构成一个 $n+1n+1$ 位的排序，且最后一位为 $jj$。我们可以采用以下方式构造：对于前 $nn$ 位中 $\ge j\backslash geq\; j$ 的数使其 $+1+1$，对于 的数保持不变

例如：对于一个长度为 $55$ 的排列 $p=53214p\; =5\backslash \; 3\; \backslash \; 2\backslash \; 1\backslash \; 4$，我们想在尾部插入数 $33$，$pp$ 通过上述变化即可变为 $642156\backslash \; 4\backslash \; 2\backslash \; 1\backslash \; 5$，且每一位的相对大小关系都没有发生变化，此时形成的新排序 $p^{\mathrm{\prime }}=642153p\text{'}\; =\; 6\backslash \; 4\backslash \; 2\backslash \; 1\backslash \; 5\backslash \; 3$

故状态设置为 $dp[i][j]dp[i][j]$ 表示前 $ii$ 个数都已经排列完成，且最后一位 $\le j\backslash leq\; j$ 的所有方案数

时间复杂度：$O(n^2)O(n^2)$

AC代码

#include <bits/stdc++.h>

using ll = long long;

constexpr int mod = 998244353;

void solve() {
    std::string s;
    std::cin >> s;

    int n = s.length();
    s = " " + s;

    std::vector<std::vector<ll>> dp(n + 2, std::vector<ll>(n + 2));

    dp[1][1] = 1;

    for (int i = 2; i <= n + 1; ++ i) {
        for (int j = 1; j <= i; ++ j) {
            if (s[i - 1] == '1') {
                dp[i][j] = dp[i - 1][j - 1];
            }
            else if (s[i - 1] == '2') {
                dp[i][j] = (dp[i - 1][i - 1] - dp[i - 1][j - 1] + mod) % mod;
            }
            else {
                dp[i][j] = dp[i - 1][i - 1];
            }
        }
        for (int j = 1; j <= i; ++ j) {
            (dp[i][j] += dp[i][j - 1]) %= mod;
        }
    }

    std::cout << dp[n + 1][n + 1] << "\n";
}

int main() {
    std::cin.tie(nullptr);
    std::ios_base::sync_with_stdio(false);

    solve();

    return 0;
}