首页 > 代码库 > 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万径人踪灭
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。