近似回文

[题目链接](https://www.nowcoder.com/practice/6da3c8db8de040e29908efd855c562ae)

思路

本题要求长度为 $n$ 的小写字母串中，满足"非回文但删去恰好一个字符后可变为回文"的串的个数，结果对 $998244353$ 取模。

双指针分析结构

对于一个非回文串 $s$ ，用双指针从两端向中间匹配： $s[0]$ 与 $s[n-1]$ ， $s[1]$ 与 $s[n-2]$ ，... 设第一个失配出现在深度 $d$ ，即 $s[i] = s[n-1-i]$ 对 $i = 0, 1, \ldots, d-1$ 成立，但 $s[d] \neq s[n-1-d]$ 。

要让删除一个字符后变为回文，只有两种可能：

删左端：删去 $s[d]$ ，需要内部子串 $s[d+1 \ldots n-1-d]$ 本身是回文。
删右端：删去 $s[n-1-d]$ ，需要内部子串 $s[d \ldots n-2-d]$ 本身是回文。

可以证明，对于任何近似回文串，有效的删除位置一定包含第一个失配处的左端或右端（或两者都可），因此按失配深度 $d$ 分类能不重不漏地枚举所有近似回文串。

分类计数

固定失配深度 $d$ ，令内部长度 $m = n - 2d$ 。

选项 A（删左端）的方案数：外层 $d$ 对匹配字符有 $26^d$ 种选法；内部回文 $s[d+1 \ldots n-1-d]$ 长度为 $m-1$ ，自由位有 $\lceil(m-1)/2\rceil$ 个，共 $26^{\lceil(m-1)/2\rceil}$ 种； $s[d]$ 可以取除 $s[n-1-d]$ 以外的任意字母（ $25$ 种）。所以：

$ $\text{CountA}(d) = 25 \cdot 26^{d + \lceil(m-1)/2\rceil}$ $

由对称性，选项 B 的方案数 $\text{CountB}(d) = \text{CountA}(d)$ 。

两者同时成立（CountAB）：此时 $s[d+1 \ldots n-1-d]$ 和 $s[d \ldots n-2-d]$ 都是长度 $m-1$ 的回文。分析可得内部必须以周期 2 交替： $s[d] = s[d+2] = s[d+4] = \cdots$ 且 $s[d+1] = s[d+3] = \cdots$ ，且 $s[d] \neq s[d+1]$ 。

$n$ 为偶数时 $m$ 为偶数，交替结构自洽： $\text{CountAB}(d) = 25 \cdot 26^{d+1}$ 。
$n$ 为奇数时 $m$ 为奇数，交替结构产生矛盾： $\text{CountAB}(d) = 0$ 。

由容斥，每个深度 $d$ 的贡献为 $\text{Count}(d) = \text{CountA}(d) + \text{CountB}(d) - \text{CountAB}(d)$ 。

化简闭合公式

关键观察：当 $n$ 为偶数， $m-1$ 为奇数， $\lceil(m-1)/2\rceil = m/2 = n/2 - d$ ，所以 $\text{CountA}(d) = 25 \cdot 26^{n/2}$ ，与 $d$ 无关！

当 $n$ 为奇数， $\lceil(m-1)/2\rceil = (m-1)/2 = (n-1)/2 - d$ ，同样 $\text{CountA}(d) = 25 \cdot 26^{(n-1)/2}$ ，与 $d$ 无关。

对所有合法深度求和：

$n$ 为偶数（ $d = 0, 1, \ldots, n/2 - 1$ ）：

$ $\text{ans} = \sum_{d=0}^{n/2-1} \left(2 \cdot 25 \cdot 26^{n/2} - 25 \cdot 26^{d+1}\right) = 26^{n/2}(25n - 26) + 26$ $

其中几何级数求和 $\sum_{d=0}^{n/2-1} 26^{d+1} = \frac{26(26^{n/2}-1)}{25}$ 。

$n$ 为奇数（ $d = 0, 1, \ldots, (n-3)/2$ ）：

$ $\text{ans} = \sum_{d=0}^{(n-3)/2} 50 \cdot 26^{(n-1)/2} = 25(n-1) \cdot 26^{(n-1)/2}$ $

特殊情况

当 $n = 1$ 时，所有串都是回文，答案为 $0$ 。

最终只需一次快速幂和常数次乘法即可求解。

代码

C++
Java
Python3
JavaScript

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 998244353;

long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

int main() {
    long long n;
    scanf("%lld", &n);
    if (n <= 1) {
        printf("0\n");
        return 0;
    }
    long long ans;
    if (n % 2 == 0) {
        long long h = n / 2;
        long long p = power(26, h, MOD);
        long long coeff = (25LL * n % MOD - 26 + MOD) % MOD;
        ans = (p % MOD * coeff % MOD + 26) % MOD;
    } else {
        long long h = (n - 1) / 2;
        long long p = power(26, h, MOD);
        ans = 25LL % MOD * ((n - 1) % MOD) % MOD * p % MOD;
    }
    printf("%lld\n", ans);
    return 0;
}

import java.util.Scanner;

public class Main {
    static final long MOD = 998244353;

    static long power(long base, long exp, long mod) {
        long result = 1;
        base %= mod;
        while (exp > 0) {
            if ((exp & 1) == 1) result = result * base % mod;
            base = base * base % mod;
            exp >>= 1;
        }
        return result;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        if (n <= 1) {
            System.out.println(0);
            return;
        }
        long ans;
        if (n % 2 == 0) {
            long h = n / 2;
            long p = power(26, h, MOD);
            long coeff = (25L * n % MOD - 26 + MOD) % MOD;
            ans = (p * coeff % MOD + 26) % MOD;
        } else {
            long h = (n - 1) / 2;
            long p = power(26, h, MOD);
            ans = 25L % MOD * ((n - 1) % MOD) % MOD * p % MOD;
        }
        System.out.println(ans);
    }
}

import sys

def power(base, exp, mod):
    return pow(base, exp, mod)

def main():
    n = int(sys.stdin.readline())
    MOD = 998244353
    if n <= 1:
        print(0)
        return
    if n % 2 == 0:
        h = n // 2
        p = power(26, h, MOD)
        coeff = (25 * n - 26) % MOD
        ans = (p * coeff + 26) % MOD
    else:
        h = (n - 1) // 2
        p = power(26, h, MOD)
        ans = 25 * (n - 1) % MOD * p % MOD
    print(ans)

main()

const readline = require('readline');
const rl = readline.createInterface({ input: process.stdin });

function power(base, exp, mod) {
    let result = 1n;
    base = base % mod;
    while (exp > 0n) {
        if (exp & 1n) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1n;
    }
    return result;
}

rl.on('line', (line) => {
    const n = BigInt(line.trim());
    const MOD = 998244353n;
    if (n <= 1n) {
        console.log("0");
        return;
    }
    let ans;
    if (n % 2n === 0n) {
        const h = n / 2n;
        const p = power(26n, h, MOD);
        const coeff = (25n * n % MOD - 26n + MOD) % MOD;
        ans = (p * coeff % MOD + 26n) % MOD;
    } else {
        const h = (n - 1n) / 2n;
        const p = power(26n, h, MOD);
        ans = 25n * ((n - 1n) % MOD) % MOD * p % MOD;
    }
    console.log(ans.toString());
});

复杂度分析

时间复杂度: $O(\log n)$ ，来自快速幂。
空间复杂度: $O(1)$ 。