题目链接：Codeforces 1178F2

世界上有 $n +1$ 种不同的颜色，从 $0$ 到 $n$ 标号。现在你有一张长度为 $m$ 的纸，所有位置的初始颜色均为 $0$。

Alice 通过如下步骤队这张纸染色。她按顺序使用颜色 $1$ 到 $n$ 染色，对于第 $i$ 种颜色，她选择两个整数 $1 \le a_i \le b_i \le m$ 满足位置 $[a_i, b_i]$ 的颜色相同，然后把区间 $[a_i, b_i]$ 都染成颜色 $i$。

通过所有操作，Alice 需要把第 $i$ 个位置染成颜色 $c_i$，你需要求出满足条件的序列对 $\{a_i\}_{i = 1} ^ {n}, \{b_i\}_{i = 1} ^ {n}$ 的数量，答案对 $998244353$ 取模。

数据范围：$1 \le n \le 500$，$n \le m \le 10 ^ 6$，$1 \le c_i \le n$，$\forall 1 \le j \le n, \exists k, c_k = j$。

Solution

对于相邻的相同颜色，只保留其中 $1$ 对答案没有影响。去重后如果长度大于 $2n$ 则一定「无解」，直接输出 $0$ 即可（每次染色最多增加 $2$ 个相邻的不同颜色）。

接下来只在「有解」的情况下讨论。

由于 $m$ 和 $n$ 同阶，直接考虑「区间 $\text{DP}$」，我们定义 $f(i, j)$ 表示区间 $[i, j]$ 的答案。对于当前区间 $[i, j]$，我们肯定最先染最小的颜色 $c$。我们预处理出每种颜色的位置集合，记为 $pos(i)$。

对于这个区间，第一次染色肯定需要包含区间 $[\min\{pos(c)\}, \max\{pos(c)\}]$。所以如果 $[\min\{pos(c)\}, \max\{pos(c)\}] \not\subseteq [i, j]$，那么 $f(i, j) = 0$。

否则我们枚举染色的左端点 $l \in [i, \min\{pos(c)\}]$，对左区间的贡献为 $L = \sum f(i, l - 1) \cdot f(l, \min\{pos(c)\} - 1)$；右区间同理计算得出 $R$，则有 $f(i, j) = L \cdot R$。

设 $pos(c) = p_1, p_2, \dots, p_{\lvert pos(c) \rvert}$，那么区间 $(p_i, p_{i +1})$ 对大区间的答案也有贡献。于是我们得到 $f(i, j)$ 的转移方程：

$$ f(i, j) = L \cdot R \cdot \prod_{i = 1} ^ {\lvert pos(c) \rvert - 1} f(p_i + 1, p_{i + 1} - 1) $$

最终答案为 $f(1, m)$， 注意初始化的一些细节问题。

时间复杂度：$O(m + n ^ 3)$。

Code

#include <cstdio>
#include <algorithm>
#include <vector>

const int N = 1e3 + 5, M = 1e6 + 5;
const int MOD = 998244353;

int n, m, a[M], f[N][N];
std::vector<int> vec[N];

void add(int &x, int y) {
    (x += y) >= MOD && (x -= MOD);
}
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) scanf("%d", &a[i]);
    m = std::unique(a + 1, a + m + 1) - (a + 1);
    if (m > 2 * n) {
        printf("0\n");
        return 0;
    }
    for (int i = 1; i <= m; i++) vec[a[i]].emplace_back(i);
    for (int i = 1; i <= m + 1; i++) f[i][i - 1] = 1;
    for (int l = 1; l <= m; l++) {
        for (int i = 1, j = l; j <= m; i++, j++) {
            int c = *std::min_element(a + i, a + j + 1);
            int x = vec[c].front(), y = vec[c].back();
            if (x < i || y > j) {
                f[i][j] = 0;
                continue;
            }
            int L = 0, R = 0;
            for (int k = i; k <= x; k++) {
                add(L, 1LL * f[i][k - 1] * f[k][x - 1] % MOD);
            }
            for (int k = y; k <= j; k++) {
                add(R, 1LL * f[y + 1][k] * f[k + 1][j] % MOD);
            }
            f[i][j] = 1LL * L * R % MOD;
            for (int k = 1; k < (int)vec[c].size(); k++) {
                if (vec[c][k - 1] + 1 < vec[c][k]) {
                    f[i][j] = 1LL * f[i][j] * f[vec[c][k - 1] + 1][vec[c][k] - 1] % MOD;
                }
            }
        }
    }
    printf("%d\n", f[1][m]);
    return 0;
}