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$

• 样例输入

• 样例输出

• 样例说明

样例中所有回文子序列按照字典序如下：

“”（空串）、”a”、”aa”、”aka”、”f”、”ff”、”k”、”kak”、”kk”、”t”

• 数据规模与约定

对于 $100\%$ 的数据，$n \leq 5000$ 。

字符串中仅包含小写字母。

 

 

 …