首页 > 代码库 > BZOJ3160万径人踪灭

BZOJ3160万径人踪灭

技术分享

技术分享

技术分享

 

题解:

题意即求不连续但间隔长度对称的回文串个数。

若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=1000000007;
type
  xs=record
    x,y:double;
  end;
  arr=array[0..270001]of xs;
var
  e,t:arr;
  a:array[1..5]of arr;
  n,m,i,ll,ans:longint;
  ch:array[-2..270001]of char;
  b:array[-2..270001]of longint;
  z,ksm:array[0..270001]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:=-1; l:=-1; b[-1]:=1;
  for i:=0 to m*2-1 do
  begin
    if l>=i then
    b[i]:=min(b[2*k-i],l-i+1)else b[i]:=1;
    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 1))mod mo;
    if i+b[i]-1>l then begin l:=i+b[i]-1; k:=i; end;
  end;
end;
procedure fft(xx:longint);
var i,j,q,k,l,c:longint;
  t:xs;
begin
  for i:=0 to n-1 do a[xx+2,z[i]]:=a[xx,i];
  xx:=xx+2;
  k:=n; l:=1;
  for i:=ll downto 1 do
  begin
    k:=k shr 1;
    for j:=0 to k-1 do
    begin
      c:=j*2*l;
      for q:=0 to l-1 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*2;
  end;
end;
begin
  readln(s); m:=length(s);
  ch[-2]:=+;
  for i:=0 to m-1 do ch[i*2]:=s[i+1];
  ch[m*2+1]:=-;
  manacher;
  for i:=0 to m-1 do if ch[i*2]=a then a[1,i].x:=1;
  for i:=0 to m-1 do if ch[i*2]=b then a[2,i].x:=1;
  n:=1;
  while n<m*2 do begin n:=n*2; inc(ll); end;
  for i:=1 to n-1 do z[i]:=(z[i shr 1]shr 1)or((i and 1)shl(ll-1));
  ksm[0]:=1; for i:=1 to 100000 do ksm[i]:=(ksm[i-1]*2)mod mo;
  for i:=0 to n-1 do e[i].x:=cos(pi*2*i/n);
  for i:=0 to n-1 do e[i].y:=sin(pi*2*i/n);
  fft(1); fft(2);
  for i:=0 to n-1 do a[3,i]:=a[3,i]*a[3,i]+a[4,i]*a[4,i];
  for i:=0 to n-1 do e[i].y:=-e[i].y;
  fft(3);
  for i:=0 to m-1 do a[5,i*2].x:=a[5,i*2].x+n;
  for i:=0 to n-1 do ans:=(ans+ksm[round(a[5,i].x/2/n)]-1)mod mo;
  writeln(ans);
end.

BZOJ3160万径人踪灭