[BZOJ3160/Luogu4199]万径人踪灭(FFT,Manacher)

发布于 2018-04-01  117 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3160/Luogu4199]万径人踪灭(FFT,Manacher)

Description

BZOJ3160-1
BZOJ3160-1

Tab

FFT,Manacher

解决思路

要求求不连续的回文子序列的数量,那么就用所有回文序列的数量(可以连续或不连续)减去回文子串的数量。
首先考虑回文子串的数量如何求,可以用Mancher求出所有位置的回文半径,然后每一个回文半径都可以组合出若干回文子串,这个可以直接计算。
然后考虑求所有可连续也可以不连续的回文子序列的个数。看一个例子,为了方便后面的求解,字符串从0开始编号。

由于回文序列的中心可能是字符也可能是字符的间隔,所以运用Manacher的思想,我们可以把字符串S补成这样S'

设F[i]为S'中以位置为i的地方为中心有几对字符相同,那么如果我们知道以i为中心的对称的a和b的数量,假设为x,我们就可以得到以i为中心的所有回文序列的个数了,即为\(2^{\frac{x}{2}}-1\),这个可以用组合原理得到。
然后我们考虑如何得到这个x。观察原串编号之间的关系,比如aba的编号分别为012,在S'中为246,于是我们可以得到这样一个式子,对于原串S中对称的两个位置(不管是关于字符对称还是间隙对称)i,j,它们的对称中心在S'中为\((i+1)+(j+1)\)。
所以我们设F[i]表示在S'中以第i个位置为对称中心的相同的字符对数,那么有
\[F[i]=\frac{\sum_{j=1} [s[i]==s[i-2-j]]+1}{2}\]
我们发现这个是一个类似卷积的形式,所以可以用\(FFT\)来做,具体来说,构造多项式的时候,分a和b两次来做,比如aba
第一次(a):\(1+0*x+1*x^2\)
第二次(b):\(0+1*x+0*x^2\)
分别自乘就可以求出对应系数,然后再用上面的公式算,最后减去用\(Manacher\)算出来的连续回文的贡献。

代码

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:[BZOJ3160/Luogu4199]万径人踪灭(FFT,Manacher)


HNCJ OIer