Codeforces

Luogu

分析

设 $dp_{i,j}$ 表示前 $i$ 个数，第 $i$ 位填 $j$ 的方案数，$s_i$ 表示 $\sum_{j=1}^k dp_{i,j}$，$len_{i,j}$ 表示第 $i$ 位往前最多有多少位为 $j$。

转移时讨论一下。当 $len_{i,j}<l$ 时 $dp_{i,j}=s_{i-1}$；否则要减去超长的那一部分，即为 $dp_{i,j}=s_{i-1}-s_{i-l}+dp_{i-l,j}$，这里加上一个 $dp_{i-l,j}$ 的原因是我们只去掉长度恰好为 $l$ 的段避免算重。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10,K=100+10;
const int mod=998244353;

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

int main() {
    n=read(),k=read(),l=read();
    for (int i=1;i<=n;++i) a[i]=read();
    for (int i=1;i<=n;++i)
        for (int j=1;j<=k;++j)
            if (a[i]==-1||a[i]==j) len[i][j]=len[i-1][j]+1;
    s[0]=1;
    for (int i=1;i<=n;++i)
        for (int j=1;j<=k;++j) {
            if (a[i]!=-1&&a[i]!=j) continue;
            if (len[i][j]<l) dp[i][j]=s[i-1];
            else dp[i][j]=((s[i-1]-s[i-l]+mod)%mod+dp[i-l][j])%mod;
            s[i]=(s[i]+dp[i][j])%mod;
        }
    printf("%d\n",s[n]);
    return 0;
}