YZOJ P2443 回文子序列
时间限制：1000MS 内存限制：131072KB
难度：\(5.0\)
-
题目描述
求一个字符串的回文子序列个数。
如果 \(p_1p_2 \cdots p_m\) 满足 \(1 \leq p_1<p_2<\cdots<p_m \leq n\)，则称 \(a_{p_1}a_{p_2}\cdots a_{p_m}\) 是序列 \(a_1a_2\cdots a_n\) 的一个子序列。
如果对于所有 \(1 \leq i \leq n\) 都满足 \(a_i=a_n-i+1\)，则 \(a\) 是一个回文串。空串也是回文串。
-
输入格式
一个字符串
-
输出格式
回文子序列个数 \(\mod 10^9+7\)
-
样例输入
|
1 |
akakfft |
-
样例输出
|
1 |
10 |
-
样例说明
样例中所有回文子序列按照字典序如下：
“”（空串）、”a”、”aa”、”aka”、”f”、”ff”、”k”、”kak”、”kk”、”t”
-
数据规模与约定
对于 \(100\%\) 的数据，\(n \leq 5000\) 。
字符串中仅包含小写字母。