「Codeforces 1140E」Palindrome-less Arrays

题意

当一个数组 $b$ 至少有一个长度为奇数的连续回文子串时，称 $b$ 是坏的，否则称 $b$ 是好的。

给你长度为 $n$ 的数组 $a$，其中 $−1$ 可替换为任意从 $1$ 到 $k$ 的整数。

求好数组的个数，对 998244353 取模。

题解

发现 $b$ 为坏的条件完全等价于 不存在长度为三的回文串，即 $a_i \neq a_{i+2}$，故考虑分奇偶处理，最后乘起来。

问题转换成 长度为 $n$ 的串，相邻数不能相等，方案有多少？

考虑分治

$a\neq b$，$f_{i,0/1}$ 表示中间 $-1$ 个数为 $i$，$1/0$ 表示两端数是否相等

• $a, -1, \dots, -1, b$ 有 $f_{i,0} = (k-2)f_{i-1,0}+f_{i-1,1}$
• $a, -1, \dots, -1, a$ 有 $f_{i,1} = (k-1)f_{i-1,0}$

特殊的 $f_{0,0} = 1, f_{0,1}=0$

最后还要考虑一些特殊情况

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define per(i, l, r) for (int i = (l); i >= (r); --i)
using std::cerr;
using std::cin;
using std::cout;
using std::endl;
using std::make_pair;
using std::pair;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned int ui;

const int p = 998244353;

const int N = 201000;

#define mod(x) (x) %= 998244353

inline int mul(int x, int y) { return ((ll)x * y) % p; }
inline int add(int x, int y) { return ((ll)x + y) % p; }

int a[N], b[N], cnta, cntb;

int k, f[N][2];

int ksm(int a, int n) {
    int ret = 1;
    while (n) {
        if (n & 1) ret = mul(ret, a);
        a = mul(a, a);
        n >>= 1;
    }
    return ret;
}

int solve(int a[], int n) {
    if (n == 0) return 1;
    int l = 0, r = n - 1;
    int ret;
    for (; a[l] == -1 && l < n; l++)
        ;
    if (l == n) return mul(k, ksm(k - 1, n - 1));
    for (; a[r] == -1; --r)
        ;
    ret = mul(ksm(k - 1, l), ksm(k - 1, n - r - 1));
    int lst = l;
    for (l = lst + 1; l <= r; ++l) {
        if (a[l] == -1) continue;
        ret = mul(ret, f[l - lst - 1][a[lst] == a[l]]);
        lst = l;
    }
    return ret;
}

int main() {
    std::ios::sync_with_stdio(false);
    cout.tie(0);
    int n;
    cin >> n >> k;

    f[0][0] = 1, f[0][1] = 0;
    rep(i, 1, n) {
        f[i][1] = mul(f[i - 1][0], k - 1);
        f[i][0] = add(mul(k - 2, f[i - 1][0]), f[i - 1][1]);
    }

    rep(i, 1, n) {
        if (i & 1)
            cin >> a[cnta++];
        else
            cin >> b[cntb++];
    }

    cout << mul(solve(a, cnta), solve(b, cntb));
    return 0;
}