Description

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$.

Idea

Let’s try dynamic programming approach to this problem. Let $f_{i,j}$ be the number of ways to replace all $−1$ with numbers from $1$ to $k$ in such a way that array $\{a_1,\cdots,a_i\}$ is good and the last number of that array is $j$, and $s_i$ be $\sum f_{i,j}$.

Then initially it’s $f_{i,j}=s_{i-1}$ if $a_i$ equals to −1−1 or $j$. However, we could include incorrect states doing this directly. To subtract all the bad states, let’s talk about when it would happen.

  1. $i≥len$, as we should have at least $len$ elements;
  2. segment $\{a_1,\cdots,a_i\}$ has all its elements either equal to $−1$ or $j$.

If both of these conditions hold then you should subtract all the bad states from $f_{i,j}$, which equals to $s_{i-len}-f_{i-len,j}$.

Code