Vasya and Array (Codeforces 1093F)
Tags: DP, dp

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

Input: 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).

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

Note: Possible answers in the first test:   $$$[1, 2, 1, 1, 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.

Sample Inputs:
5 2 3
1 -1 1 -1 2

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

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

Sample Outputs:
2

0

645711643

Solution (Python):
def vasya_and_array():
    (n, k, leng) = [int(x) for x in input().split()]
    if leng == 1:
        return 0
    a = [int(x) for x in input().split()]
    mod = 998244353
    a.insert(0, 0)
    dp = [[0 for x in range(k + 1)] for y in range(n + 1)]
    sumdp = [0 for _ in range(n + 1)]
    sumdp[0] = 1
    count = [0 for _ in range(k + 1)]
    for i in range(1, n + 1):
        for j in range(1, k + 1):
            if a[i] == -1 or a[i] == j:
                dp[i][j] = sumdp[i - 1]
                count[j] += 1
                if count[j] >= leng:
                    dp[i][j] -= sumdp[i - leng] - dp[i - leng][j]
                dp[i][j] %= mod
                sumdp[i] += dp[i][j]
                sumdp[i] %= mod
            else:
                count[j] = 0
    return sumdp[n]
print(vasya_and_array())

Solution (Python):
from sys import stdin
input = lambda : stdin.readline()[:-1]
(n, m, L) = map(int, input().split())
a = list(map(lambda x: int(x) - 1, input().split()))
mod = 998244353
memo = [[0] * m for i in range(n)]
cnt = [0] * m
dp = [0] * m
for i in range(n):
    ndp = [0] * m
    if i == 0:
        if a[i] != -2:
            memo[i][a[i]] = 1
            cnt[a[i]] = 1
            ndp[a[i]] = 1
        else:
            for j in range(m):
                memo[i][j] = 1
                cnt[j] = 1
                ndp[j] = 1
    elif a[i] != -2:
        cnt[a[i]] += 1
        s = sum(dp) % mod
        ndp[a[i]] = s
        memo[i][a[i]] = (s - dp[a[i]]) % mod
    else:
        s = sum(dp) % mod
        for j in range(m):
            memo[i][j] = (s - dp[j]) % mod
            cnt[j] += 1
            ndp[j] = s
    if i + 1 - L >= 0:
        for j in range(m):
            if cnt[j] == L:
                ndp[j] -= memo[i + 1 - L][j]
        if a[i + 1 - L] != -2:
            cnt[a[i + 1 - L]] -= 1
        else:
            for j in range(m):
                cnt[j] -= 1
    dp = [i % mod for i in ndp]
ans = sum(dp) % mod
print(ans)

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
(n, k, l) = map(int, input().split())
a = [-1] + list(map(int, input().split()))
mod = 998244353
powk = [1]
for _ in range(n):
    powk.append(k * powk[-1] % mod)
inv = pow(k, mod - 2, mod)
invk = [1]
for _ in range(n):
    invk.append(inv * invk[-1] % mod)
cntk = [0] * (n + 1)
for i in range(1, n + 1):
    if not a[i] ^ -1:
        cntk[i] = 1
    cntk[i] += cntk[i - 1]
c = cntk[n]
dp = [[0] * (k + 1) for _ in range(l)]
dpsum = [0] * l
cnt = [0] * (k + 1)
s = set()
for i in range(1, l):
    ai = a[i]
    if not ai ^ -1:
        continue
    s.add(ai)
    cnt[ai] += 1
ans = powk[c]
for i in range(l, n + 1):
    ai = a[i]
    dpi = [0] * (k + 1)
    if ai ^ -1:
        cnt[ai] += 1
        s.add(ai)
    x = c + cntk[i - l] - cntk[i]
    if not len(s) ^ 1 and (not x ^ c):
        ans = 0
        break
    (px, ix) = (powk[x], invk[c - x])
    z = cntk[n] - cntk[i]
    (pz, iz) = (powk[z], invk[z])
    if not len(s) ^ 1:
        j = list(s)[0]
        u = (dp[i - 1][j] - dp[i - l][j]) % mod * pz % mod
        v = dpsum[i - l] * ix % mod
        dpi[j] = (px - (u + v)) % mod * iz % mod
    elif not len(s):
        v = dpsum[i - l] * ix % mod
        for j in range(1, k + 1):
            u = (dp[i - 1][j] - dp[i - l][j]) % mod * pz % mod
            dpi[j] = (px - (u + v)) % mod * iz % mod
    sdp = 0
    dp0 = dp[-1]
    for j in range(1, k + 1):
        sdp += dpi[j] * pz % mod
        sdp %= mod
        dpi[j] += dp0[j]
        dpi[j] %= mod
    ans -= sdp
    ans %= mod
    dp.append(dpi)
    dpsum.append((dpsum[-1] + sdp) % mod)
    ai = a[i - l + 1]
    if ai ^ -1:
        cnt[ai] -= 1
        if not cnt[ai]:
            s.remove(ai)
print(ans)