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
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; } |