字符串的回文化代价之和

题目分析

给定长度为 n 的字符串 s，需要算出它的所有非空子序列的回文化代价之和，对 10^9+7 取模。回文化代价指把一个字符串改成回文串时，最少要修改多少字符。

对于一个子序列 t，改成回文的代价等于它两端对应位置上不相等的字符对数。

算法思路

我们把所有子序列的代价值，拆到原串中每一对位置 i < j 上：

1. 只有当 s[i] ≠ s[j] 时，这对才会在某些子序列里各自作为一对不匹配，贡献 1。
2. 要让位置 i 和 j 在子序列中正好构成一对对称位置，需要：
   • 原串的 i 和 j 都被选中；
   • 在 i 之前和 j 之后各选出相同数目的字符，使它们对应上下层；
   • i 与 j 之间的字符任意选或不选。

设 i 之前有 A=i，j 之后有 C=n–1–j，i 和 j 之间有 B=j–i–1，则

• i,j 都选中并在同一层的选法数是 “从 A+C 个位置里选 A 个” ，即 C(A+C, A)；
• 中间 B 个位置的选法是 2^B。

所以当 s[i]≠s[j] 时，这对 (i,j) 对总答案的贡献是

C(i-1 + (n-1-j), i-1) * 2^(j-i-1)

将所有 i<j 且 s[i]≠s[j] 的贡献累加，取模即可。

复杂度分析

• 预处理阶乘和逆阶乘：O(n)
• 枚举 i<j：O(n²)
• 总时间 O(n²)，n≤200 时足够快，空间 O(n)。

代码实现

Python

def solve():
    M = 10**9 + 7
    s = input().strip()
    n = len(s)
    # 预处理阶乘和逆阶乘
    fac = [1]*(n+1)
    ifac = [1]*(n+1)
    for i in range(1, n+1):
        fac[i] = fac[i-1] * i % M
    # 快速幂求逆元：a^{-1} = a^{M-2} mod M
    def modpow(a, e):
        r = 1
        while e:
            if e & 1: r = r * a % M
            a = a * a % M
            e >>= 1
        return r
    ifac[n] = modpow(fac[n], M-2)
    for i in range(n, 0, -1):
        ifac[i-1] = ifac[i] * i % M
    # 预处理 2^k
    pow2 = [1]*(n+1)
    for i in range(1, n+1):
        pow2[i] = pow2[i-1] * 2 % M
    # 组合数
    def comb(x, y):
        if y<0 or y>x: return 0
        return fac[x] * ifac[y] % M * ifac[x-y] % M

    ans = 0
    for i in range(n):
        for j in range(i+1, n):
            if s[i] != s[j]:
                A = i
                C = n-1-j
                B = j-i-1
                ans = (ans + comb(A+C, A) * pow2[B]) % M
    print(ans)

if __name__ == "__main__":
    solve()

Java

import java.util.*;
public class Main {
    static final int M = 1_000_000_007;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int n = s.length();
        // 预处理阶乘和逆阶乘
        long[] fac = new long[n+1], ifac = new long[n+1];
        fac[0] = 1;
        for (int i = 1; i <= n; i++) {
            fac[i] = fac[i-1] * i % M;
        }
        ifac[n] = modPow(fac[n], M-2);
        for (int i = n; i >= 1; i--) {
            ifac[i-1] = ifac[i] * i % M;
        }
        // 预处理 2^k
        long[] pow2 = new long[n+1];
        pow2[0] = 1;
        for (int i = 1; i <= n; i++) {
            pow2[i] = pow2[i-1] * 2 % M;
        }
        long ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                if (s.charAt(i) != s.charAt(j)) {
                    int A = i;
                    int C = n-1-j;
                    int B = j-i-1;
                    ans = (ans + comb(fac, ifac, A+C, A) * pow2[B]) % M;
                }
            }
        }
        System.out.println(ans);
    }
    // 快速幂
    static long modPow(long a, long e) {
        long r = 1;
        while (e > 0) {
            if ((e & 1) == 1) r = r * a % M;
            a = a * a % M;
            e >>= 1;
        }
        return r;
    }
    // 组合数
    static long comb(long[] fac, long[] ifac, int x, int y) {
        if (y<0 || y>x) return 0;
        return fac[x] * ifac[y] % M * ifac[x-y] % M;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
const int M = 1e9+7;

long modpow(long a, long e) {
    long r = 1;
    while (e) {
        if (e & 1) r = r * a % M;
        a = a * a % M;
        e >>= 1;
    }
    return r;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s;
    cin >> s;
    int n = s.size();
    // 预处理阶乘和逆阶乘
    vector<long> fac(n+1,1), ifac(n+1,1);
    for (int i = 1; i <= n; i++) {
        fac[i] = fac[i-1] * i % M;
    }
    ifac[n] = modpow(fac[n], M-2);
    for (int i = n; i >= 1; i--) {
        ifac[i-1] = ifac[i] * i % M;
    }
    // 预处理 2^k
    vector<long> pow2(n+1,1);
    for (int i = 1; i <= n; i++) {
        pow2[i] = pow2[i-1] * 2 % M;
    }

    auto comb = [&](int x, int y)->long {
        if (y < 0 || y > x) return 0;
        return fac[x] * ifac[y] % M * ifac[x-y] % M;
    };

    long ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j < n; j++) {
            if (s[i] != s[j]) {
                int A = i;
                int C = n-1-j;
                int B = j-i-1;
                ans = (ans + comb(A+C, A) * pow2[B]) % M;
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

题目内容

我们定义一个字符串的 “回文化代价” 为将该字符串直接修改成回文串（不允许重排字符）所需的最小字符修改次数。

现给定字符串 $s$，请你求出 $s$ 的所有非空子序列的 “回文化代价” 之和，并将结果对 $10^9+7$ 取模后输出。

【名词解释】

• 子序列：子序列为从原序列中删除任意个（可以为零、可以为全部）元素得到的新序列。
• 回文串：正读或倒读均相同的字符串。
• 字符修改：将一个字符修改成另一个字符的操作。

输入描述

输入一行，包含一个字符串 $s$，其中 $s$ 仅由小写英文字母构成，且满足 $1\leq |s|\leq 200$，其中 $|s|$ 表示 $s$ 的长度。

输出描述

输出一个整数，表示 $s$ 的所有非空子序列的回文化代价之和对 $10^9+7$ 取模后的结果。

示例1

输入

aba

输出

2

说明

字符串 "$aba$" 的非空子序列共有 $2^3-1=7$ 个，它们分别为：

1. "$a$"：回文化代价为 $0$；
2. "$b$"：回文化代价为 $0$；
3. "$a$"：回文化代价为 $0$；
4. "$ab$"：字符分别为 $'a'$ 和 $'b'$，回文化代价为 $1$；
5. "$aa$"：字符均为 $'a'$，回文化代价为 $0$；
6. "$ba$"：字符分别为 $'b'$ 和 $'a'$，回文化代价为 $1$；
7. "$aba$"：比较首尾字符 $'a'$ 和 $'a'$，故回文化代价为 $0$。

因此，总和为 $0+0+0+1+0+1+0=2$。

示例2

输入

abb

输出

3

说明

字符串 "$abb$" 的非空子序列共有 $2^3-1=7$ 个，它们分别为：

1. "$a$"：回文化代价为 $0$；
2. "$b$"：回文化代价为 $0$；
3. "$b$"：回文化代价为 $0$；
4. "$ab$"：字符为 $'a'$ 和 $'b'$，回文化代价为 $1$；
5. "$ab$"：另一种选法，同样回文化代价为 $1$；
6. "$bb$"：两个字符均为 $'b'$，回文化代价为 $0$；
7. "$abb$"：比较首尾字符 $'a'$ 和 $'b'$，回文化代价为 $1$。

因此，总和为 $0+0+0+1+1+0+1=3$。

示例3

输入

aabbccddee

输出

2176