CF1093F

CF1093F

题解

• 容斥

• 设 \(dp(i, j)\) 为考虑到 \(i\) 位置，该位置填 \(j\) 的方案数

• 分类讨论

  • 如果 \(a[i] != -1\)
    • 如果 \(j = a[i]\)， \(dp(i, j) = \sum 前面的总方案数\)
    • 否则 \(dp(i, j) = 0\)
  • 如果 \(a[i] = -1\)
    • \(dp(i, j) = \sum 前面的总方案数\)
  • 前面的总方案数设为 \(sum_i = \sum_{j = 1}^{k} dp(i, k)\)

• 再考虑不符合要求的部分

  • 如果 \(i\) 前面有的长度 \(\ge len\) 的由 \(j\) 或 \(-1\) 组成的连续段，即 \(a[i - len] 到 a[i - 1] = j 或 -1\)
  • \(dp(i, j) = sum_{i - 1} - sum_{i - len} + dp(i - len, j)\)
    • \([i - len, i - 1]\) 全都取 \(j\) 的方案数为 \(sum_{i - len}\)
    • 但是如果这样取，在 \(i - len\) 取到的 \(j\) 已经使得后面的 \([i - len, i - 1]\) 构成不合法序列
    • 所以再加上 \(dp(i - len, j)\)

代码

# include <bits/stdc++.h>
# define int long long
using namespace std;
const int MOD = 998244353;
const int N = (int)1e5 + 10;
const int K = (int)1e2 + 10;

int n, k, len;
int a[N];
int dp[N][K], sum[N];
int s[K][N];

signed main(){
	cin >> n >> k >> len;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		if(a[i] == -1){
			for(int j = 1; j <= k; j++){
				s[j][i]++;
			}
		}else{
			s[a[i]][i]++;
		}
	}
	
	for(int i = 1; i <= k; i++){
		for(int j = 1; j <= n; j++){
			if(s[i][j] == 0){
				s[i][j] = 0;
			}else{
				s[i][j] += s[i][j - 1];
			}
		}
	}
	
	dp[0][0] = 1, sum[0] = 1;
	for(int i = 1; i <= n; i++){
		if(a[i] != -1){
			int j = a[i], num = s[j][i];
			if(num >= len){		
				dp[i][j] = (sum[i - 1] - sum[i - len] + dp[i - len][j] + MOD) % MOD;
			}else{
				dp[i][j] = sum[i - 1];
			}
		}else{
			for(int j = 1; j <= k; j++){
				int num = s[j][i];
				if(num >= len){		
					dp[i][j] = (sum[i - 1] - sum[i - len] + dp[i - len][j] + MOD) % MOD;
				}else{
					dp[i][j] = sum[i - 1];
				}
			}
		}
		for(int j = 1; j <= k; j++){
			(sum[i] += dp[i][j]) %= MOD;
		}
	}
	cout << sum[n] << "\n";
}