Description
Input & Output & Sample Input & Sample Output
HINT
题解:
题意即求不连续但间隔长度对称的回文串个数。
若si=sj,则这对字符可以作为以(i+j)/2为中心的回文串的一部分。
用F[i]来表示可以做为以i/2为中心的回文串的一部分的字符对数,则以i/2为中心的回文串数为2^F[i]。
则这就成了多项式乘法:先做一次a的,把字符为a的位置值赋为1,其余为0,进行一次FFT;同理做一次b的。
因为完全连续是不可以的,所以用Manacher求出这样的回文串的个数并减去。
代码:
(BZOJ上PASCAL跑得不够快,再加上这题时限只有10s,并没有AC,不知道那些用PASCAL通过的人是怎么卡常数的)
uses math;
const
mo=;
type
xs=record
x,y:double;
end;
arr=array[..]of xs;
var
e,t:arr;
a:array[..]of arr;
n,m,i,ll,ans:longint;
ch:array[-..]of char;
b:array[-..]of longint;
z,ksm:array[..]of longint;
s:ansistring;
operator -(a,b:xs)c:xs;
begin c.x:=a.x-b.x; c.y:=a.y-b.y; end;
operator +(a,b:xs)c:xs;
begin c.x:=a.x+b.x; c.y:=a.y+b.y; end;
operator *(a,b:xs)c:xs;
begin c.x:=a.x*b.x-a.y*b.y; c.y:=a.x*b.y+a.y*b.x; end;
procedure manacher;
var k,l,i:longint;
begin
k:=-; l:=-; b[-]:=;
for i:= to m*- do
begin
if l>=i then
b[i]:=min(b[*k-i],l-i+)else b[i]:=;
while true do
begin
if ch[i+b[i]]=ch[i-b[i]] then inc(b[i])
else break;
end;
ans:=(ans+mo-(b[i]shr ))mod mo;
if i+b[i]->l then begin l:=i+b[i]-; k:=i; end;
end;
end;
procedure fft(xx:longint);
var i,j,q,k,l,c:longint;
t:xs;
begin
for i:= to n- do a[xx+,z[i]]:=a[xx,i];
xx:=xx+;
k:=n; l:=;
for i:=ll downto do
begin
k:=k shr ;
for j:= to k- do
begin
c:=j**l;
for q:= to l- do
begin
t:=e[q*k]*a[xx,c+l];
a[xx,c+l]:=a[xx,c]-t;
a[xx,c]:=a[xx,c]+t;
inc(c);
end;
end;
l:=l*;
end;
end;
begin
readln(s); m:=length(s);
ch[-]:='+';
for i:= to m- do ch[i*]:=s[i+];
ch[m*+]:='-';
manacher;
for i:= to m- do if ch[i*]='a' then a[,i].x:=;
for i:= to m- do if ch[i*]='b' then a[,i].x:=;
n:=;
while n<m* do begin n:=n*; inc(ll); end;
for i:= to n- do z[i]:=(z[i shr ]shr )or((i and )shl(ll-));
ksm[]:=; for i:= to do ksm[i]:=(ksm[i-]*)mod mo;
for i:= to n- do e[i].x:=cos(pi**i/n);
for i:= to n- do e[i].y:=sin(pi**i/n);
fft(); fft();
for i:= to n- do a[,i]:=a[,i]*a[,i]+a[,i]*a[,i];
for i:= to n- do e[i].y:=-e[i].y;
fft();
for i:= to m- do a[,i*].x:=a[,i*].x+n;
for i:= to n- do ans:=(ans+ksm[round(a[,i].x//n)]-)mod mo;
writeln(ans);
end.
PASCAL
#include<bits/stdc++.h>
using namespace std;
int mo=;
typedef pair<double,double> pa;
pa operator + (pa a,pa b)
{ pa c; c.first=a.first+b.first; c.second=a.second+b.second; return c; }
pa operator - (pa a,pa b)
{ pa c; c.first=a.first-b.first; c.second=a.second-b.second; return c; }
pa operator * (pa a,pa b)
{ pa c; c.first=a.first*b.first-a.second*b.second; c.second=a.first*b.second+a.second*b.first; return c; }
pa a[][],e[];
char s[],s2[];
int n,ans,nn,m,ksm[],z[];
void manacher()
{
int l=,k=; z[]=;
for(int i=;i<=nn;i++)
{
if(l>=i)z[i]=min(z[*k-i],l-i);else z[i]=;
while(s2[i+z[i]+]==s2[i-z[i]-])z[i]++;
ans=(ans-(z[i]+)/)%mo; if(i+z[i]>l){ k=i; l=i+z[i]; }
}
}
void fft(int x)
{
for(int i=;i<m;i++)a[x+][z[i]]=a[x][i]; x++;
for(int k=m/,i=;i<m;i*=,k/=) for(int j=;j<m;j+=*i) for(int l=;l<i;l++)
{ pa t=e[k*l]*a[x][j+l+i]; a[x][j+l+i]=a[x][j+l]-t; a[x][j+l]=a[x][j+l]+t; }
}
int main()
{
scanf("%s",s+); n=strlen(s+); nn=; s2[]='!'; s2[]='*';
for(int i=;i<=n;i++){ nn++; s2[nn]=s[i]; nn++; s2[nn]='*'; } s2[nn+]='?';
manacher();
ksm[]=; for(int i=;i<=;i++)ksm[i]=ksm[i-]*%mo;
m=; while(m<*n)m=m*;
for(int i=;i<m;i++)z[i]=(z[i>>]>>)+(i&)*m/;
e[].first=; e[].first=cos(*acos(-)/m); e[].second=sin(*acos(-)/m);
for(int i=;i<m;i++)e[i]=e[i-]*e[];
for(int i=;i<=n;i++)if(s[i]=='a')a[][i-].first=; fft();
for(int i=;i<=n;i++)if(s[i]=='b')a[][i-].first=; fft();
for(int i=;i<m;i++)a[][i]=a[][i]*a[][i]+a[][i]*a[][i];
for(int i=;i<m;i++)e[i].second=-e[i].second;
fft();
for(int i=;i<m;i++)ans=(ans+ksm[((int)round(a[][i].first/m)+)/]-)%mo;
ans=(ans+mo)%mo;
printf("%d\n",ans);
}
C++