CF 1093F Vasya and Array

题目描述

https://codeforces.com/problemset/problem/1093/F

简要题意：给定一个长度为 $n$ 的序列 $a_i$ 以及 $k$ 和 $L$，$a_i\in[1,k]$ 或者 $a_i=-1$，对于 $a_i=-1$ 的点，你需要填一个 $[1,k]$ 的数字，满足不存在长度大于等于 $L$​ 的连续相等段

$n \le 10^5,k\le 100$

Solution

我们考虑容斥 $dp$，令 $f[i][j]$ 表示前 $i$ 个数字已经填完，第 $i$ 个数字是 $j$，$g[i]=\sum_{j=1}^k f[i][j]$

转移的时候，我们枚举第 $i$ 位填数字 $j$，然后将不合法的情况减掉，容易得到不合法的情况就是 $g[i-L]-f[i-L][j]$

时间复杂度 $O(nk)$

#include <iostream>
#include <algorithm>
#define maxn 100010
#define maxm 110
#define ll long long
using namespace std;

const int p = 998244353;

inline int add(int x, int y) { return (x += y) >= p ? x - p : x; } 

int n, m, L, a[maxn], l[maxm];

int f[maxn][maxm], g[maxn];
int main() { 
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m >> L;
    for (int i = 1; i <= n; ++i) cin >> a[i];
    g[0] = 1; 
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j)
            if (a[i] == -1 || a[i] == j) ++l[j];
            else l[j] = 0;
        for (int j = 1; j <= m; ++j) {
            if (a[i] > 0 && a[i] != j) continue;
            f[i][j] = g[i - 1];
            if (l[j] >= L) f[i][j] = add(f[i][j], p - add(g[i - L], p - f[i - L][j]));
            g[i] = add(g[i], f[i][j]);
        }
    } cout << g[n] << "\n";
    return 0;
}