Palindrome-less Arrays
Contest: Educational Codeforces Round 62 (Rated for Div. 2)
Difficulty rating: 2200
Tags: combinatorics, divide and conquer, dp

Let's denote that some array $$$b$$$ is bad if it contains a subarray $$$b_l, b_{l+1}, \dots, b_{r}$$$ of odd length more than $$$1$$$ ($$$l < r$$$ and $$$r - l + 1$$$ is odd) such that $$$\forall i \in \{0, 1, \dots, r - l\}$$$ $$$b_{l + i} = b_{r - i}$$$.

If an array is not bad, it is good.

Now you are given an array $$$a_1, a_2, \dots, a_n$$$. Some elements are replaced by $$$-1$$$. Calculate the number of good arrays you can obtain by replacing each $$$-1$$$ with some integer from $$$1$$$ to $$$k$$$.

Since the answer can be large, print it modulo $$$998244353$$$.

Input format:
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n, k \le 2 \cdot 10^5$$$) — the length of array $$$a$$$ and the size of "alphabet", i. e., the upper bound on the numbers you may use to replace $$$-1$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$a_i = -1$$$ or $$$1 \le a_i \le k$$$) — the array $$$a$$$.

Output format:
Print one integer — the number of good arrays you can get, modulo $$$998244353$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
2 3
-1 -1

Example output:
9

Example input:
5 2
1 -1 -1 1 2

Example output:
0

Editorial:
At first, "array contains a palindromic subarray of length $$$\ge 3$$$" is equivalent to "array contains a palindromic subarray of length $$$=3$$$". So we need to calculate number of arrays without palindromes of length $$$3$$$. It's equivalent to finding arrays where $$$a[i] \neq a[i + 2]$$$ for all appropriate $$$i$$$.
Note, that $$$i$$$ and $$$i + 2$$$ have same parity, so all odd and all even positions in array are independent, and answer is the product of the number of ways to choose numbers for odd positions, and the number of ways to choose numbers for even positions.
In terms of same parity our condition morphs to $$$a[i] \neq a[i + 1]$$$ and we need to calculate all ways to replace ($$$-1$$$)-s in such way that all pairs of consecutive elements are different.
To calculate it let's look at sequences of consecutive ($$$-1$$$)-s. They will look like $$$a, -1, -1, \dots, -1, b$$$ with $$$l$$$ ($$$-1$$$)-s, where $$$a$$$ and $$$b$$$ are positive (case where $$$a$$$ is empty can be considered as $$$k \cdot (a, -1, \dots, -1, b \text{ with $$$l - 1$$$ ($$$-1$$$)-s})$$$, case with empty $$$b$$$ is solved the same way).
In the end we need to find a way to calculate the number of those sequences. There are only two fundamental types of sequences: $$$a, -1, \dots, -1, a$$$ (same value from both ends) and $$$a, -1, \dots, -1, b$$$ ($$$a \neq b$$$). Exact values of $$$a$$$ and $$$b$$$ don't really matter.
Let's find a way to calculate both values (name them $$$cntSame$$$ and $$$cntDiff$$$) for $$$l$$$ consecutive ($$$-1$$$)-s in $$$O(\log{l})$$$ time. Base values: $$$cntSame(0) = 0, cntDiff(0) = 1$$$.
Let's try to choose value of $$$-1$$$ in the middle of sequence: if $$$l \mod 2 = 1$$$, then we can split sequence in two sequences of length $$$\lfloor l / 2 \rfloor$$$ and $$$cntSame(l) = cntSame(l / 2)^2 + (k - 1) \cdot cntDiff(l / 2)^2$$$ and $$$cntDiff(l) = 2 \cdot cntSame(l / 2) \cdot cntDiff(l / 2) + (k - 2) \cdot cntDiff(l / 2)^2$$$.
If $$$l \mod 2 = 0$$$ then just iterate over value of last $$$-1$$$, then $$$cntSame(l) = (k - 1) \cdot cntDiff(l - 1)$$$ and $$$cntDiff(l) = cntSame(l - 1) + (k - 2) \cdot cntDiff(l - 1)$$$.
Resulting complexity is $$$O(n)$$$.