CF1140E Palindrome-less Arrays

我们称一个数组 $b$ 是坏的，如果它包含一个长度大于 $1$ 的奇数长度子数组 $b_l, b_{l+1}, \dots, b_r$（$l < r$ 且 $r - l + 1$ 为奇数），并且满足 $\forall i \in \{0, 1, \dots, r - l\}$，都有 $b_{l + i} = b_{r - i}$。 如果一个数组不是坏的，则称它是好的。 现在给定一个数组 $a_1, a_2, \dots, a_n$，其中有些元素被替换成了 $-1$。你需要计算通过将每个 $-1$ 替换为 $1$ 到 $k$ 之间的某个整数后，可以得到多少个好的数组。 由于答案可能很大，请输出答案对 $998244353$ 取模后的结果。

第一行包含两个整数 $n$ 和 $k$（$2 \le n, k \le 2 \cdot 10^5$），分别表示数组 $a$ 的长度和“字母表”的大小，即你可以用来替换 $-1$ 的最大数字。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$a_i = -1$ 或 $1 \le a_i \le k$），表示数组 $a$。

输出一个整数，表示可以得到的好的数组的数量，对 $998244353$ 取模。

由 ChatGPT 4.1 翻译