CodeForces

题意：N,K,L，以及给定长度为N的序列，表示其对应的颜色，-1表示还没有涂色，现在让你去涂色，使得最后没有大于等于L的连续的同色的情况。

思路：我们用dp[i][j]表示第i个位置颜色为j的合法方案数，用sum[i]表示dp[i][1]+dp[i][2]+...dp[i][k]。

那么a[i]==j或者-1时，dp[i][j]=sum[i-1]-x。然后我们考虑到可能有不合法的情况x，当且仅当前面有长度为L的序列颜色为j或者-1时，其数量为sum[i-L]-sum[i-L][j]，减去后面这个sum[i-L][j]是因为它长度为L+1了，那么之前已经减去了。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int Mod=998244353;
const int maxn=100010;
int a[maxn],dp[maxn][101],sum[maxn],len[101];
int main()
{
    int N,K,L;
    scanf("%d%d%d",&N,&K,&L);
    rep(i,1,N) scanf("%d",&a[i]);
    sum[0]=1;
    rep(i,1,N){
        rep(j,1,K) len[j]=(a[i]==-1||a[i]==j)?len[j]+1:0;
        if(a[i]==-1){
            rep(j,1,K) {
                dp[i][j]=sum[i-1];
                if(len[j]>=L) dp[i][j]=(dp[i][j]-(sum[i-L]-dp[i-L][j]+Mod)%Mod+Mod)%Mod;
            }
        }
        else  {
            dp[i][a[i]]=sum[i-1];
            if(len[a[i]]>=L) dp[i][a[i]]=(dp[i][a[i]]-(sum[i-L]-dp[i-L][a[i]]+Mod)%Mod+Mod)%Mod;
        }
        rep(j,1,K) sum[i]=(sum[i]+dp[i][j])%Mod;
    }
    printf("%d
",sum[N]);
    return 0;
}