题解：AT_arc187_b [ARC187B] Sum of CC

这一场先过了 B 再过了 A /fendou

性质 1：一个连通分量内点的编号连续。

证明：反证法，设 l<i<r 使得 l,r 在一个连通分量内但 i 不在这个连通分量内。

所以我们知道 f(A)=1+\sum_{i=1}^{n-1}[i,i+1\text{ 不在一个连通分量内}]。

性质 2：i,i+1 不在一个连通分量内 \iff \min_{j=1}^i A_j>\max_{j=i+1}^n A_j。

左推右：反证法，若 \min_{j=1}^i A_j\le\max_{j=i+1}^n A_j，则存在 1\le p\le i<i+1\le q\le n 使得 A_p\le A_q，此时因为 A_p,A_q 是最小值，我们有 A_p\le A_i,A_{i+1}\le A_q，则 i,i+1 之间存在路径 i\to p\to q\to i+1。

右推左：反证法，取 i,i+1 间任意一条路径中任意一条跨过 i,i+1 的边 (p,q)，此时有 A_p\le A_q 且 p\le i<i+1\le q，则此时有 \min_{j=1}^iA_i\le A_p\le A_q\le\max_{j=i+1}^nA_j，与假设矛盾。

现在我们枚举 i 与 x=\min_{j=1}^iA_j，用 DP 算出前缀的 B_i 选择的方案数（需要后缀和优化），对于后缀，显然应当满足 \max_{j=i+1}^nB_j<x，则此时若后缀有 y 个 -1，后缀的方案数就是 (x-1)^y。

时间复杂度为 O(nm)，可以通过此题。

#include <cstdio>
using namespace std;
typedef long long ll;
const ll mod = 998244353;
const int N = 2005;
ll f[N][N], suf[N][N], pow[N][N];
int b[N], suf_max[N], suf_cnt[N];
int max(int a, int b) {
    return a > b ? a : b;
}
int main() {
//  freopen("in.txt", "r", stdin);
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &b[i]);
    }
    for (int i = n; i >= 1; i--) {
        suf_max[i] = max(suf_max[i + 1], b[i]);
        suf_cnt[i] = suf_cnt[i + 1];
        if (b[i] == -1) {
            suf_cnt[i]++;
        }
    }
    for (int i = 0; i <= m; i++) {
        pow[i][0] = 1;
        for (int j = 1; j <= n; j++) {
            pow[i][j] = pow[i][j - 1] * i % mod;
        }
    }
    f[0][m] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= 1; j--) {
            suf[i - 1][j] = (suf[i - 1][j + 1] + f[i - 1][j]) % mod;
        }
        if (b[i] == -1) {
            for (int j = 1; j <= m; j++) {
                f[i][j] = (suf[i - 1][j] + f[i - 1][j] * (m - j)) % mod;
            }
        } else {
            for (int j = 1; j < b[i]; j++) {
                f[i][j] = f[i - 1][j];
            }
            for (int j = b[i]; j <= m; j++) {
                f[i][b[i]] = (f[i][b[i]] + f[i - 1][j]) % mod;
            }
        }
    }
    ll ans = 0;
    for (int i = 1; i < n; i++) {
        for (int j = suf_max[i + 1] + 1; j <= m; j++) {
            ans = (ans + pow[j - 1][suf_cnt[i + 1]] * f[i][j]) % mod;
        }
    }
    ll add = 1;
    for (int i = 1; i <= n; i++) {
        if (b[i] == -1) {
            add = add * m % mod;
        }
    }
    printf("%lld", (ans + add) % mod);
    return 0;
}