题目大意
传送门
给一个字符串$s$，对于$s$的每一个前缀$t$，判断$t$是否能够拆分为$1\rightarrow 31$个非空回文串，使用二进制输出。
题目分析
回文自动机优化动规模板题。
代码
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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
| #include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;
inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {
if(x=='-')bj=-1;
x=getchar();
}
while(isdigit(x)) {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}
const int maxn=300005;
struct Palindsome_Automaton {
int child[maxn][26];
int n,size,last,s[maxn],len[maxn],next[maxn],diff[maxn],snext[maxn];
Palindsome_Automaton() {
size=-1;
newnode(0);
newnode(-1);
last=n=0;
s[0]=-1;
next[0]=next[1]=1;
}
int newnode(int v) {
int now=++size;
len[now]=v;
return now;
}
void insert(int data) {
s[++n]=data;
int p=last;
while(s[n-len[p]-1]!=s[n])p=next[p];
if(!child[p][data]) {
int now=newnode(len[p]+2),q=next[p];
while(s[n-len[q]-1]!=s[n])q=next[q];
next[now]=child[q][data];
child[p][data]=now;
diff[now]=len[now]-len[next[now]];
snext[now]=diff[now]==diff[next[now]]?snext[next[now]]:next[now];
}
last=child[p][data];
}
} pam;
char s[maxn];
int n;
unsigned int f[maxn],series[maxn];
int main() {
scanf("%s",s+1);
n=strlen(s+1);
f[0]=1;
for(int i=1; i<=n; i++) {
pam.insert(s[i]-'a');
for(int v=pam.last; pam.len[v]>0; v=pam.snext[v]) {
series[v]=f[i-(pam.len[pam.snext[v]]+pam.diff[v])];
if(pam.diff[v]==pam.diff[pam.next[v]])series[v]|=series[pam.next[v]];
f[i]|=series[v]<<1;
}
printf("%u\n",f[i]>>1);
}
return 0;
}
|
