Codeforces 1093F Vasya and Array

有点迷的容斥 + DP……

设 fi,j 表示第 i 个位置为 j 的方案数，并有 si=k∑j=1fi,j。

首先只有 ai=j 或 ai=−1 的时候 fi,j 有意义。
那么先不考虑限制条件，直接从 si−1 继承所有方案。
然鹅有限制，显然当同时满足以下两点时有不合法状态： 1. i≥len。 2. ai−len+1,…,ai 这一段可以通过修改 −1 为 j 变成一样的。

这个时候，不合法的状态是 si−len−fi−len,j。
之所以要多算一个 fi−len,j，是因为各种容斥，会把它多减一次。

代码：

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5;
const int K = 100;
const int mod = 998244353;
int n,k,len;
int a[N + 5],cnt[N + 5][K + 5],f[N + 5][K + 5],s[N + 5];
int main()
{
    s[0] = 1;
    scanf("%d%d%d",&n,&k,&len);
    for(register int i = 1;i <= n;++i)
    {
        scanf("%d",a + i);
        for(register int j = 1;j <= k;++j)
        {
            cnt[i][j] = cnt[i - 1][j] + (a[i] == j || a[i] == -1);
            if(a[i] == j || a[i] == -1)
                f[i][j] = ((s[i - 1] - (i >= len && cnt[i][j] - cnt[i - len][j] == len ? ((s[i - len] - f[i - len][j]) % mod + mod) % mod : 0)) % mod + mod) % mod;
            s[i] = (s[i] + f[i][j]) % mod;
        }
    }
    printf("%d\n",s[n]);
}