显然一对位置在(x,y)权值相等的字符会对(x+y)/2这个位置产生1的贡献，然后每个位置求出2的权值次方减去1求和，再减去连续的回文串即可，前者跑两次FFT，后者跑一个manacher即可。显然一对位置在(x,y)权值相等的字符会对(x+y)/2这个位置产生1的贡献，然后每个位
阅读背景：
bzoj 3160 万径人踪灭 - FFT - manacher
来源：互联网
分享到：
