隐藏
「bzoj3160」万径人踪灭 - 生成函数+Manacher/回文自动机 | Bill Yang's Blog

路终会有尽头,但视野总能看到更远的地方。

0%

「bzoj3160」万径人踪灭 - 生成函数+Manacher/回文自动机

题目大意

    给定一个仅由ab构成的字符串,求其位置关于某条对称轴对称的不完全连续回文串。


题目分析

正向思考比较困难,考虑补集转化。
位置关于某条对称轴对称的不完全连续回文串$=$位置关于某条对称轴对称的任意回文串$-$连续回文串。

其中,连续回文串数目是很好求的,直接上马拉车算法或回文自动机。
因此,只需考虑如何求出 位置关于某条对称轴对称的任意回文串 数目。

如图,我们枚举每一个对称轴,求出其最长可非连续回文长度,也就是有多少个字母能够对称。
上图的最长可非连续回文长度为$3$,故一共能形成$2^3-1=7$个位置关于对称轴对称的任意回文串(考虑每个字母选与不选,除去空串)。
因此,我们现在需要求出以每个对称轴对称的最长可非连续回文长度$f[i]$。
朴素的求法是$O(n^2)$的。

我们将串进行扩展,使其能够表示出间隙。
如例中$s=$ababaaab扩展为$s’=$a#b#a#b#a#a#a#b
考虑,若$s_0=a$与$s_5=a$关于$s_{2.5}$的间隙对称,也就是$s’_5$。
因此:

其中除以$2$是因为对称每个字母会被算两次,$+1$是因为如果对称轴在字母上只会计算一次。

令:

则:

$g[i]$很明显是一个卷积,我们可以先将$s$转化为多项式:

  • 将$a$变为$1$,$b$变为$0$,如样例$s=ababaaab$,转化为多项式: 对多项式进行平方,对应项系数记为$g_1[i]$。
  • 将$b$变为$1$,$a$变为$0$,如样例$s=ababaaab$,转化为多项式: 对多项式进行平方,对应项系数记为$g_2[i]$。

因此$g[i]=g_1[i]+g_2[i]$。
问题解决。


代码

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<complex>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

#define cp complex<double>
typedef long long LL;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=262144+5;
const LL mod=1e9+7;
const double pi=acos(-1);

struct FastFourierTransform {
int n;
cp omega[maxn],iomega[maxn];

void init(int n) {
this->n=n;
for(int i=0; i<n; i++) {
omega[i]=cp(cos(2*pi/n*i),sin(2*pi/n*i));
iomega[i]=conj(omega[i]);
}
}

void transform(cp* a,cp* omega) {
int k=log2(n);
for(int i=0; i<n; i++) {
int t=0;
for(int j=0; j<k; j++)if(i&(1<<j))t|=(1<<(k-j-1));
if(i<t)swap(a[i],a[t]);
}
for(int len=2; len<=n; len*=2) {
int mid=len>>1;
for(cp* p=a; p!=a+n; p+=len)
for(int i=0; i<mid; i++) {
cp t=omega[n/len*i]*p[mid+i];
p[mid+i]=p[i]-t;
p[i]+=t;
}
}
}

void dft(cp* a) {
transform(a,omega);
}

void idft(cp* a) {
transform(a,iomega);
for(int i=0; i<n; i++)a[i]/=n;
}
} fft;

void Multiply(const int* a1,const int n1,const int* a2,const int n2,int* ans) {
int n=1;
while(n<n1+n2)n<<=1;
static cp c1[maxn],c2[maxn];
fill(c1,c1+n,0);
fill(c2,c2+n,0);
for(int i=0; i<n1; i++)c1[i].real(a1[i]);
for(int i=0; i<n2; i++)c2[i].real(a2[i]);
fft.init(n);
fft.dft(c1);
fft.dft(c2);
for(int i=0; i<n; i++)c1[i]*=c2[i];
fft.idft(c1);
for(int i=0; i<n1+n2-1; i++)ans[i]+=round(c1[i].real());
}

struct Palindsome_Automaton {
int child[maxn][28];
int n,size,last,s[maxn],len[maxn],next[maxn];
LL cnt[maxn];
Palindsome_Automaton() {
size=-1;
newnode(0); //even
newnode(-1); //odd
last=n=0;
s[0]=-1;
next[0]=next[1]=1;
}
int newnode(int v) {
int now=++size;
memset(child[now],0,sizeof(child[now]));
next[now]=0;
len[now]=v;
return now;
}
void insert(int data,int id) {
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;
}
last=child[p][data];
cnt[last]++;
}
void build(string s) {
int tot=0;
for(auto x:s)insert(x-'a',++tot);
}
void count() {
for(int i=size; i>=0; i--)cnt[next[i]]+=cnt[i];
}
} pam;

char s[maxn];
int len,a[maxn],b[maxn],f[maxn];
LL bit[maxn],ans=0;

int main() {
scanf("%s",s);
len=strlen(s);
bit[0]=1;
for(int i=1; i<=len; i++)bit[i]=(bit[i-1]<<1)%mod;
for(int i=0; i<len; i++)a[i]=b[i]=s[i]=='a';
Multiply(a,len,b,len,f);
for(int i=0; i<len; i++)a[i]=b[i]=s[i]=='b';
Multiply(a,len,b,len,f);
for(int i=0; i<=2*len-2; i++)ans=(ans+bit[(f[i]+1)>>1]-1)%mod;
pam.build(s);
pam.count();
for(int i=2; i<=pam.size; i++)ans=(ans-pam.cnt[i]%mod+mod)%mod;
printf("%lld\n",ans);
return 0;
}
姥爷们赏瓶冰阔落吧~