有点迷的容斥 + DP……
设 \(f_{i,j}\) 表示第 \(i\) 个位置为 \(j\) 的方案数，并有 \(s_i = \sum\limits_{j = 1}^k f_{i,j}\)。
首先只有 \(a_i = j\) 或 \(a_i = -1\) 的时候 \(f_{i,j}\) 有意义。
那么先不考虑限制条件，直接从 \(s_{i - 1}\) 继承所有方案。
然鹅有限制，显然当同时满足以下两点时有不合法状态： 1. \(i \ge len\)。 2. \(a_{i - len + 1},\dots,a_i\) 这一段可以通过修改 \(-1\) 为 \(j\) 变成一样的。
这个时候，不合法的状态是 \(s_{i - len} - f_{i - len,j}\)。
之所以要多算一个 \(f_{i - len,j}\)，是因为各种容斥，会把它多减一次。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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]);
}