题解 CF1093F 【Vasya and Array】
XG_Zepto
2018-12-18 20:26:58
首发于 [个人博客](https://zepto.page/post/codeforces-1093f)。
### 思路
我们可以使用 $DP$ 解决这个问题。令 $f_{i,j}$ 为考虑前 $i$ 个数，第 $i$ 个数为 $j$ 的合法方案数，$s_i$ 等于 $\sum f_{i,j}$。
那么，$f_{i,j}$ 一定从 $s_{i-1}$ 转移而来，如果 $a_j$ 恰好等于 $j$ 或者 $-1$ 的话。但是，直接转移会包含不合法的情况。我们考虑，一些状态不合法，当且仅当：
1. $i≥len$;
2. 子区间 $\{a_1,\cdots,a_i\}$ 中所有的元素都等于 $−1$ 或者 $j$。
发现，满足以上两个条件的状态数实际上就是 $s_{i-len}-f_{i-len,j}$。转移的时候删去即可。
### 代码
```cpp
#include <bits/stdc++.h>
#define md 998244353
#define maxn 100001
#define max(a,b) (a>b?a:b)
#define maxk 101
int n,k,len,a[maxn];
int f[maxn][maxk],s[maxn],cnt[maxn][maxk];
void inc(int &a,int b){a=((a+b>=md)?a+b-md:a+b);}
int main(){
scanf("%d%d%d",&n,&k,&len);
for (register int i=1;i<=n;++i)
scanf("%d",&a[i]);
for (register int i=1;i<=n;++i)
for (register int j=1;j<=k;++j)
inc(cnt[i][j],cnt[i-1][j]+(a[i]==j||a[i]==-1));
for (register int i=1;i<=n;++i){
for (register int j=1;j<=k;++j){
if (!(a[i]==j||a[i]==-1)) continue;
int add=1;
if (i>1) add=s[i-1];
inc(f[i][j],add);
bool ok=i>=len;
int l=max(1,i-len+1);
ok&=(cnt[i][j]-cnt[l-1][j]==len);
if (!ok) continue;
if (i==len) {inc(f[i][j],md-1);continue;}
int sum=f[i-len][j];
inc(sum,md-s[i-len]);
inc(f[i][j],sum);
}
for (register int j=1;j<=k;++j)
inc(s[i],f[i][j]);
}
printf("%d\n",s[n]);
}
```