字符串的回文化代价之和

题目分析

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

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

算法思路

题目内容

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

现给定字符串 $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