CF1093F Vasya and Array [DP+容斥]

本文主要是介绍CF1093F Vasya and Array [DP+容斥]，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门

我们令 f[i][k] 表示到 i , 最后一位为k的答案

, 减去不合法的答案

如果 i-len+1---- i 之间要么是 -1，要么是 j，那么就有可能不合法

j 可以接到 第 i-len的任意一个后面，所以 

但是我们前一位可能就已经将不合法的 j 剪掉了，因为每当到不合法的第一个位置就会被剪掉

所以 

---

#include<bits/stdc++.h>
#define N 100050
#define M 105
using namespace std;
typedef long long ll;
const int Mod = 998244353;
ll f[N][M], s[N];
int sum[N][M], n, k, len, a[N];
ll add(ll a, ll b){ return (a+b) % Mod;}
ll mul(ll a, ll b){ return (a*b) % Mod;}
int main(){scanf("%d%d%d", &n, &k, &len);if(len == 1){ printf("0"); return 0;} for(int i=1; i<=n; i++){scanf("%d", &a[i]);for(int j=1; j<=k; j++){sum[i][j] = sum[i-1][j] + (a[i] == j || a[i] == -1);}}if(a[1] == -1) for(int i=1; i<=k; i++) f[1][i] = 1, s[1] += f[1][i];else f[1][a[1]] = 1, s[1] = 1; s[0] = 1;for(int i=2; i<=n; i++){for(int j=1; j<=k; j++){if(a[i] != -1 && a[i] != j) continue;f[i][j] = s[i-1];if(i >= len){ int pos = i - len;if(sum[i][j] - sum[pos][j] == len){f[i][j] = add(f[i][j], Mod - add(s[pos], Mod - f[pos][j]));} } s[i] = add(s[i], f[i][j]);}} printf("%lld", s[n]); return 0;
}

 

这篇关于CF1093F Vasya and Array [DP+容斥]的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---