考虑朴素的 DP:令 (dp(i,j,k)) 表示到第 (i) 个,当前数字为 (k),连续的长度为 (j) 的方案数。如果接下来要接上数字 (x) ,就可以得到以下转移:
[dp(i,j,x)
ightarrow dp(i+1,j+1,x)\
dp(i,?,?)
ightarrow dp(i+1,1,x)\
]
第一种转移相当于将所有的下标全部右移,第二种相当于更新第一个位置。
看到右移这个操作不难想到用队列优化,每次将最后面的弹出,然后在最前面 push 一个新的值即可。
(k) 很小所以显然可以存下。
const int N=2e5+5;
const int K=1e2+5;
int n,k,len,a[N];
int all;
struct que {
int l,r,tag,sum,_[N<<1];
inline int truly(int x) {return x<tag?_[x]:0;}
inline void init() {l=N+1,r=N+len-1,sum=0,tag=inf;}
inline void update() {--l,pls(sum,_[l]=dec(all,sum)),sub(sum,truly(r)),--r;}
inline void clear() {sum=0,tag=l;}
} q[K];
int main() {
IN(n,k,len);
lep(i,1,n) IN(a[i]);
lep(i,1,k) q[i].init();
lep(t,1,n) {
all=(t==1);
lep(i,1,k) pls(all,q[i].sum);
if(a[t]==-1) lep(i,1,k) q[i].update();
else {
q[a[t]].update();
lep(i,1,k) if(a[t]!=i) q[i].clear();
}
}
int ans=0;
lep(i,1,k) pls(ans,q[i].sum);
printf("%d
",ans);
return 0;
}