Vasya and Array

题意翻译

给出一段长度为 $n$ 的整数序列，一个正整数 $k$ ，一个正整数 $len$ ，序列中的所有数均在 $1$ ~$k$ 之间，或者等于 $-1$。 如果没有长度大于等于 $len$ 的连续相同数字则该数段是好的。 可以将 $-1$ 改为所有 $1$ ~$k$ 之间的整数，将该数列变为好的，求出方案数，对 $998244353$ 取模

题目描述

Vasya has got an array consisting of $ n $ integers, and two integers $ k $ and $ len $ in addition. All numbers in the array are either between $ 1 $ and $ k $ (inclusive), or equal to $ -1 $ . The array is good if there is no segment of $ len $ consecutive equal numbers. Vasya will replace each $ -1 $ with some number from $ 1 $ to $ k $ (inclusive) in such a way that the resulting array is good. Tell him the number of ways to do this replacement. Since the answer may be large, print it modulo $ 998244353 $ .

输入输出格式

输入格式

The first line contains three integers $ n, k $ and $ len $ ( $ 1 \le n \le 10^5, 1 \le k \le 100, 1 \le len \le n $ ). The second line contains $ n $ numbers — the array. Each number is either $ -1 $ or between $ 1 $ and $ k $ (inclusive).

输出格式

Print one integer — the number of ways to replace each $ -1 $ with some number from $ 1 $ to $ k $ (inclusive) so the array is good. The answer may be large, so print it modulo $ 998244353 $ .

输入输出样例

输入样例 #1

5 2 3
1 -1 1 -1 2

输出样例 #1

2

输入样例 #2

6 3 2
1 1 -1 -1 -1 -1

输出样例 #2

0

输入样例 #3

10 42 7
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1

输出样例 #3

645711643

说明

Possible answers in the first test: 1. $ [1, 2, 1, 1, 2] $ ; 2. $ [1, 2, 1, 2, 2] $ . There is no way to make the array good in the second test, since first two elements are equal. There are too many answers in the third test, so we won't describe any of them.

题意翻译

给出一段长度为 $n$ 的整数序列，一个正整数 $k$ ，一个正整数 $len$ ，序列中的所有数均在 $1$ ~$k$ 之间，或者等于 $-1$。 如果没有长度大于等于 $len$ 的连续相同数字则该数段是好的。 可以将 $-1$ 改为所有 $1$ ~$k$ 之间的整数，将该数列变为好的，求出方案数，对 $998244353$ 取模