哥们不会组合数学。
首先类似这题，得出没有回文串的充要条件是没有长度为 3 的回文串。
长度为 3 的回文串，\(a_i,a_{i+1},a_{i+2}\)，只要满足 \(a_i \neq a_{i+2}\) 即可，也就是说奇数位、偶数位抠出来，新数组中相邻的数不相同。
考虑 dp，一种显然的 dp 是设 \(f_{i,j}\) 为 \([1,i]\) 中，\(a_i = j\) 的方案数。
这个时候我们发现值域有保证 \(1 \le a_i \le k\)，也就是给定的数也在 \([1,k]\) 范围内，和未确定的数的范围是一样的。
这种同值域就可以让我们进行组合数学。
从整体上看，方案数的贡献是来自于一段连续的 -1（只有它们产生了变量），所以考虑只看连续的 -1 段，然后组合起来。
-1 段可能有些限制，也可能没有限制。
没有限制（两边都没有数字），长度为 \(n\) 的 -1 段的方案数就是 \(k \times (k-1)^{n-1}\)。
有一端有数 \(x\)，说明这一端开始的一位不能和数 \(x\) 一样，而数 \(x\) 一定在 \([1,k]\) 中，所以方案数是 \((k-1)^n\)。
两端都有数 \(x, y\)，这个时候难以直接推式子，考虑dp。
这种较为复杂的组合数学的 dp，一般采用记忆化搜索，可以让分讨变得比较简洁。
首先看一下边界，如果 \(x = y\)，那么为 \(k - 1\)，否则为 \(k - 2\)。
看 \(n \ge 2\) 的情况，比如 \(n = 2\)，发现如果最后一位是 \(x\)，那么转移是 \(k - 1\)，对应 \(n = 1, x' = y'\) 的情况，而且此时要满足 \(x \neq y\)；如果最后一位不是 \(x\)，那么对应 \(n = 1, x' \neq y'\) 的情况。我们发现 \(x\) 和 \(y\) 相不相等影响了我们的转移，而且难以讨论，所以加到状态里面。
设 \(dp_{i, 0/1}\) 分别表示 \([1,i]\) 中 \(x=y\) 和 \(x \neq y\) 的方案数。
考虑 \(dp_i\) 怎么转成 \(dp_{i-1}\) 的方案，我们发现此时 \(a_i\) 才是与 \(a_{i-1}\) 相邻的数，而非 \(y\)。
如果 \(x = y\)，那么 \(y\) 和 \(a_i\) 必然不相等（相邻），\(x\) 和 \(a_i\) 必然不相等，可以从 \(dp_{i-1,1} \times (k - 1)\) 转移过来。
如果 \(x \neq y\)，那么 \(x\) 和 \(a_i\) 可以相等，此时 \(a_i\) 固定，方案是 \(dp_{i-1,0}\)，也可以不相等，当然 \(a_i\) 也不能等于 \(y\)，所以 \(a_i\) 有 \(k-2\) 种取值，方案是 \(dp_{i-1,1}\times (k - 2)\)。
有点恶心……
- Palindrome-less Palindrome Arrays lesspalindrome-less palindrome arrays less palindrome-less 题解palindrome arrays 001d palindrome palindrome version blocks 1335e super-palindrome palindrome version 1527b game operations palindrome leetcode array palindrome delayed 1136 palindrome cheapest p2890 usaco