题解：AT_arc187_b [ARC187B] Sum of CC

我们先来证一个重要的结论：每个连通块的节点的编号一定是连续的。

要证明这个结论，我们需要说明若 i 和 j 之间有连边，则 i 到 j 的所有点都在同个连通块上。显然，我们有 a_i \leq a_j，我们对 i < k < j 的所有 k 分类讨论，若 a_k \leq a_j，则 k 与 j 有连边，若 a_k > a_j，则必有 a_i \leq a_k，故 k 与 i 有连边。至此，结论得证。

我们设有 num 个 i 与 i + 1 不在一个联通块上，则答案为 1 + num。考虑什么情况下 i 与 i + 1 对答案有贡献，显然需要满足 \min\limits^{i}_{j = 1}a_j > \max\limits^{n}_{j = i + 1}a_j，因此我们对于每一个 i，枚举其前缀最小值再计算有多少种情况有贡献就可以了。

具体而言，先预处理出前缀最小值 Min 与后缀最大值 Max，再预处理出 pre 与 suf 分别表示一段前缀有多少个可变点以及一段后缀有多少个可变点。

然后，我们枚举当前位置 i 的前缀最小值 j，显然 j 的范围只能是 [Max_{i + 1} + 1, Min_i]。而要对答案有贡献，后面 suf_{i + 1} 个点显然只能在 [1, j - 1] 范围取，即有 (j - 1)^{suf_{i + 1}} 种情况。前面 pre_i 个点的取值情况需要分讨一下。

当 j = Min_i 时，是简单的，这 pre_i 个点只需要在 [j, m] 的范围内即可，一共有 (m - j + 1)^{pre_i} 种情况。否则，这 pre_i 个点中必须要有若干个点变成 j，剩余点在 [j, m] 的范围内即可。

但是若干点是多少个点呢？不知道。所以就只能枚举，这样复杂度就达到了 O(n^2m)，过不了。因此我们考虑预处理一个 dp_{i, j}，表示有 i 个点的取值范围为 [1, m]，且他们的最小值为 j 的方案数，这样我们的答案即为 dp_{pre_i, j}。

怎么转移呢？显然有 dp_{i, j} = dp_{i - 1, j} \times (m - j + 1) + \sum\limits^{m}_{k = j + 1}dp_{i - 1, k}。前面一坨表示当前最小值已经达到了 j，那当前点只需要在 [j, m] 任取即可。后面一坨表示当前最小值还未达到 j，那当前点必选 j。观察式子，容易发现加上一个后缀和优化后可以做到 O(1) 转移。

#include<bits/stdc++.h>
using namespace std;
#define SF scanf
#define PF printf
#define int long long
const int mod = 998244353;
int qkpow(int a, int b) {
    int ans = 1;
    while(b) {
        if(b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
int a[2005], pre[2005], suf[2005], Min[2005], Max[2005], dp[2005][2005], Suf[2005][2005];
signed main() {
    int n, m;
    SF("%lld%lld", &n, &m);
    for(int i = 1; i <= m; i++) dp[1][i] = 1, Suf[1][i] = m - i + 1;
    for(int i = 2; i <= n; i++) {
        for(int j = m; j; j--) {
            dp[i][j] = (dp[i - 1][j] * (m - j + 1) % mod + Suf[i - 1][j + 1]) % mod;
            Suf[i][j] = (Suf[i][j + 1] + dp[i][j]) % mod;
        }
    }
    Min[0] = m, Max[n + 1] = 1;
    for(int i = 1; i <= n; i++) SF("%lld", &a[i]), pre[i] = pre[i - 1] + (a[i] == -1), Min[i] = min(Min[i - 1], a[i] == -1 ? m : a[i]);
    for(int i = n; i; i--) suf[i] = suf[i + 1] + (a[i] == -1), Max[i] = max(Max[i + 1], a[i]);
    int ans = 0;
    for(int i = 1; i < n; i++) {
        for(int j = Min[i]; j > Max[i + 1]; j--) {
            if(j == Min[i]) ans = (ans + qkpow(j - 1, suf[i + 1]) * qkpow(m - j + 1, pre[i]) % mod) % mod;
            else ans = (ans + qkpow(j - 1, suf[i + 1]) * dp[pre[i]][j] % mod) % mod;
        }
    }
    PF("%lld", (ans + qkpow(m, pre[n])) % mod);
    return 0;
}