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

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


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

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

Description

BZOJ3160-1
BZOJ3160-1

Tab

FFT,Manacher

解决思路

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

01234
abaab

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

01234
abaab
$#a#b#a#a#b#
012345678901

设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\)算出来的连续回文的贡献。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<complex>
#include<cmath>
using namespace std;

#define ll long long
#define ld long double
#define mem(Arr,x) memset(Arr,x,sizeof(Arr))

const int maxN=200100*4;
const ld Pi=acos(-1);
const int Mod=1e9+7;
const int inf=2147483647;

int N,L;
char str[maxN],str2[maxN];
complex<ld> A[maxN],B[maxN];
ll F[maxN],Rev[maxN],Bin[maxN],H[maxN];

void FFT(complex<ld> *P,int opt);
ll Manacher();

int main()
{
    ios::sync_with_stdio(false);
    cin>>str;
    int len=strlen(str);

    for (N=1;N<=len*2+1;N=N<<1) L++;
    for (int i=0;i<N;i++) Rev[i]=(Rev[i>>1]>>1)|((i&1)<<(L-1));//Rader排序

    for (int i=0;i<len;i++) A[i]=str[i]=='a',B[i]=str[i]=='b';//分别构造多项式
    FFT(A,1);FFT(B,1);//FFT求解卷积
    for (int i=0;i<N;i++) A[i]=A[i]*A[i],B[i]=B[i]*B[i];
    for (int i=0;i<N;i++) A[i]=A[i]+B[i];
    FFT(A,-1);
    for (int i=2;i<2*len+1;i++) F[i]=(ll)((A[i-2].real()+0.5)/N+1)>>1;

    ll Ans=0;
    Bin[0]=1;for (int i=1;i<2*len+1;i++) Bin[i]=(Bin[i-1]<<1)%Mod;
    for (int i=0;i<2*len+1;i++) Ans=(Ans+Bin[F[i]]-1)%Mod;

    printf("%lld\n",(Ans+Mod-Manacher())%Mod);
}

void FFT(complex<ld> *P,int opt)//FFT
{
    for (int i=0;i<N;i++) if (i<Rev[i]) swap(P[i],P[Rev[i]]);
    for (int i=1;i<N;i=i<<1)
    {
        int dl=i<<1;
        complex<ld> dw(cos((ld)Pi/(ld)i),(ld)opt*sin(Pi/(ld)i));
        for (int j=0;j<N;j=j+dl)
        {
            complex<ld> w(1,0);
            for (int k=0;k<i;k++,w=w*dw)
            {
                complex<ld> X=P[j+k],Y=w*P[j+k+i];
                P[j+k]=X+Y;P[j+k+i]=X-Y;
            }
        }
    }
    return;
}

ll Manacher()//Manacher算连续回文的贡献
{
    int l=1;str2[0]='$';str2[1]='#';
    int len=strlen(str);
    for (int i=0;i<len;i++){
        str2[++l]=str[i];str2[++l]='#';
    }
    ll id=0,mx=0;
    for (int i=0;i<=l;i++)
    {
        if (i<=mx) H[i]=min(H[id*2-i],mx-i);
        else H[i]=1;
        while (str2[i+H[i]]==str2[i-H[i]]) H[i]++;
        if (i+H[i]>mx){
            mx=i+H[i];id=i;
        }
    }
    ll sum=0;
    for (int i=0;i<=l;i++) sum=(sum+(ll)H[i]/2)%Mod;
    return sum;
}

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

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


HNCJ OIer