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\) 。
字符串中仅包含小写字母。
典型的序列自动机。
正反字符串建立两个序列自动机，当 \(x+y \leq n\) 时能表示一个偶串， \(x+y-1 \leq n\) 时能表示一个奇串。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 |
#include <cstdio> #include <cstdlib> #include <cstring> #include <climits> #define MOD 1000000007 char s[5050]; int pos[5050][30],posr[5050][30]; bool vis[5005][5005]; int f[5005][5005]; int N; int DFS(register int x,register int y) { if(x+y > N+1) return 0; if(vis[x][y]) return f[x][y]; vis[x][y]=true; register int tans=1+(x+y<=N); for(register int j=0;j<26;j++) if(pos[x][j] && posr[y][j]) (tans+=DFS(pos[x][j],posr[y][j]))>=MOD?tans-=MOD:0; return f[x][y]=tans; } int main() { scanf("%s",&s[1]); register int ls=strlen(&s[1]); N=ls; for(register int i=ls;i>=1;i--) { for(register int j=0;j<26;j++) pos[i-1][j]=pos[i][j],posr[i-1][j]=posr[i][j]; pos[i-1][s[i]-'a']=i,posr[i-1][s[ls-i+1]-'a']=i; } DFS(0,0); printf("%d\n",(f[0][0]-1+MOD)%MOD); return 0; } |