YZOJ P2443 回文子序列

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\) 。

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

 

 

 


 

 

 

典型的序列自动机。

正反字符串建立两个序列自动机,当 \(x+y \leq n\) 时能表示一个偶串, \(x+y-1 \leq n\) 时能表示一个奇串。

CJK – next[][26].html

 

 

 

 

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注