[ARC187B] Sum of CC 题解

若 \(i\) 与 \(j\) 有边，也就是 \(a_i<a_j\)，那么对于一个 \(i < k < j\)，会发现 \(a_k>a_i\) 和 \(a_k<a_j\) 至少满足一个。也就是说 \(k\) 也一定和 \(i,j\) 联通。于是我们发现了一个关键性质：所有联通块都为一个区间。

那我们考虑 \(i\) 和 \(i+1\) 什么时候不联通：\(i\) 之前的任意一个数都大于 \(i\) 之后的任意一个数。也就是前缀 \(\min\) 大于后缀 \(\max\) 的时候。

那就可以先用 dp 预处理出前 \(i\) 个数的前缀 \(\min\) 为 \(j\) 的方案数，后缀同理。因为联通块数其实就是有多少个 \(i\) 和 \(i+1\) 不联通，所以直接枚举 \(i\) 然后用 dp 值统计答案即可。需要前缀和优化。

//dzzfjldyqqwsxdhrdhcyxll
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 2e3 + 10;
const int mod = 998244353;
int n,m,a[MAXN],f[MAXN][MAXN],sum[MAXN][MAXN],ans,g[MAXN][MAXN];
signed main() {
	cin >> n >> m;
	for(int i = 1;i <= n;i++) cin >> a[i];
	f[0][m] = 1,sum[0][0] = f[0][0];
	for(int i = 1;i <= m;i++) 
		sum[0][i] = (sum[0][i - 1] + f[0][i]) % mod;
	for(int i = 1;i <= n;i++) {
		for(int j = 1;j <= (a[i] == -1 ? m : a[i]);j++) {
			f[i][j] = f[i - 1][j] * (a[i] == -1 ? (m - j + 1) : 1) % mod;
			if(j == a[i] || a[i] == -1) f[i][j] = (f[i][j] + sum[i - 1][m] - sum[i - 1][j] + mod) % mod;
		}
		for(int j = 1;j <= m;j++) sum[i][j] = (sum[i][j - 1] + f[i][j]) % mod;
	}
	memset(sum,0,sizeof sum);
	g[n + 1][0] = 1,sum[n + 1][0] = g[n + 1][0];
	for(int i = 1;i <= m;i++) 
		sum[n + 1][i] = (sum[n + 1][i - 1] + g[n + 1][i]) % mod;
	for(int i = n;i >= 1;i--) {
		for(int j = (a[i] == -1 ? 1 : a[i]);j <= m;j++) {
			g[i][j] = g[i + 1][j] * (a[i] == -1 ? j : 1) % mod;
			if(j == a[i] || a[i] == -1) g[i][j] = (g[i][j] + sum[i + 1][j - 1]) % mod;
		}
		for(int j = 1;j <= m;j++) sum[i][j] = (sum[i][j - 1] + g[i][j]) % mod;
	}
	for(int i = 1;i <= n;i++) 
		for(int j = 1;j <= m;j++) 
			ans = (ans + f[i][j] * sum[i + 1][j - 1]) % mod;
	cout << ans;
	return 0;
}