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通过的人是怎么卡常数的）

1 uses math; 2 const 3   mo=1000000007; 4 type 5   xs=record 6     x,y:double; 7   end; 8   arr=array[0..270001]of xs; 9 var10   e,t:arr;11   a:array[1..5]of arr;12   n,m,i,ll,ans:longint;13   ch:array[-2..270001]of char;14   b:array[-2..270001]of longint;15   z,ksm:array[0..270001]of longint;16   s:ansistring;17 operator -(a,b:xs)c:xs;18 begin c.x:=a.x-b.x; c.y:=a.y-b.y; end;19 operator +(a,b:xs)c:xs;20 begin c.x:=a.x+b.x; c.y:=a.y+b.y; end;21 operator *(a,b:xs)c:xs;22 begin c.x:=a.x*b.x-a.y*b.y; c.y:=a.x*b.y+a.y*b.x; end;23 procedure manacher;24 var k,l,i:longint;25 begin26   k:=-1; l:=-1; b[-1]:=1;27   for i:=0 to m*2-1 do28   begin29     if l>=i then30     b[i]:=min(b[2*k-i],l-i+1)else b[i]:=1;31     while true do32     begin33       if ch[i+b[i]]=ch[i-b[i]] then inc(b[i])34       else break;35     end;36     ans:=(ans+mo-(b[i]shr 1))mod mo;37     if i+b[i]-1>l then begin l:=i+b[i]-1; k:=i; end;38   end;39 end;40 procedure fft(xx:longint);41 var i,j,q,k,l,c:longint;42   t:xs;43 begin44   for i:=0 to n-1 do a[xx+2,z[i]]:=a[xx,i];45   xx:=xx+2;46   k:=n; l:=1;47   for i:=ll downto 1 do48   begin49     k:=k shr 1;50     for j:=0 to k-1 do51     begin52       c:=j*2*l;53       for q:=0 to l-1 do54       begin55         t:=e[q*k]*a[xx,c+l];56         a[xx,c+l]:=a[xx,c]-t;57         a[xx,c]:=a[xx,c]+t;58         inc(c);59       end;60     end;61     l:=l*2;62   end;63 end;64 begin65   readln(s); m:=length(s);66   ch[-2]:='+';67   for i:=0 to m-1 do ch[i*2]:=s[i+1];68   ch[m*2+1]:='-';69   manacher;70   for i:=0 to m-1 do if ch[i*2]='a' then a[1,i].x:=1;71   for i:=0 to m-1 do if ch[i*2]='b' then a[2,i].x:=1;72   n:=1;73   while n

1 #include
       
         2 using namespace std; 3 int mo=1000000007; 4 typedef pair
        
          pa; 5 pa operator + (pa a,pa b) 6 { pa c; c.first=a.first+b.first; c.second=a.second+b.second; return c; } 7 pa operator - (pa a,pa b) 8 { pa c; c.first=a.first-b.first; c.second=a.second-b.second; return c; } 9 pa operator * (pa a,pa b)10 { pa c; c.first=a.first*b.first-a.second*b.second; c.second=a.first*b.second+a.second*b.first; return c; }11 pa a[5][270005],e[270005];12 char s[270005],s2[270005];13 int n,ans,nn,m,ksm[270005],z[270005];14 void manacher()15 {16     int l=1,k=1; z[1]=0;17     for(int i=2;i<=nn;i++)18     {19         if(l>=i)z[i]=min(z[2*k-i],l-i);else z[i]=0;20         while(s2[i+z[i]+1]==s2[i-z[i]-1])z[i]++;21         ans=(ans-(z[i]+1)/2)%mo; if(i+z[i]>l){ k=i; l=i+z[i]; }22     }23 }24 void fft(int x)25 {26     for(int i=0;i
         
          >1]>>1)+(i&1)*m/2;38     e[0].first=1; e[1].first=cos(2*acos(-1)/m); e[1].second=sin(2*acos(-1)/m);39     for(int i=2;i