BZOJ3160:万径人踪灭 Manachar+FFT

思路:

我连第一步都没想到T_T 首先就是答案等于所有的回文子序列减去连续的回文子序列.而连续的回文子序列我们可以轻易地利用一次Manacher在\(O(n)\)的时间复杂度得到.那么我们要求的就是所有的回文子序列.

不妨枚举对称轴,令\(f_i\)表示对称轴为\(i\)时的两边相同的元素个数.则不难发现这个对称轴对于答案的贡献为\(2^{f_i}-1\).

接下来的问题就是如何快速求出\(f_i\).

我们可以暴力,\(O(n^2)\)滚粗.

我们可以利用数据性质,例如\(a,b\)的数目有一种很少的时候,比如\(a\)很少,那么我就枚举每个\(a\)和每个\(b\)来计算对于对应对称轴负的贡献.这样时间复杂度为\(O(n_a*n_b)\).

下面考虑用FFT求出\(f_i\).

比如说字符串下标为0,1,2,3,4,5,6,令\(g(i,j)\)表示第\(i\)个位置是否为\(j\),若是则返回1,否则返回0.

则我们得到:

\[f(0)=g(0,a)g(0,a)+g(0,b)g(0,b)\]

\[f(1)=g(0,a)g(1,a)+g(0,b)g(1,b)\]

\[f(2)=g(0,a)g(2,a)+g(1,a)g(1,a)+g(0,b)g(2,b)+g(1,b)g(1,b)\]

...

我们发现\(g(i,a)\)和\(g(i,b)\)完全可以独立计算.此外我们还发现,这其实就是一个卷积少了一半的形式.我们求出卷积后\(O(1)\)就能得到真正的答案.

这样我们可以最终求出\(f_i\),最后\(O(n)\)统计.

总的时间复杂度为\(O(nlogn)\).

#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
  
static const int mod=(1e9)+7;
  
typedef double f2;
static const f2 pi=acos(-1);
  
typedef long long LL;
  
struct Cpx{
    f2 x,y;
    Cpx(){}
    Cpx(f2 _x,f2 _y):x(_x),y(_y){}
    Cpx operator+(const Cpx&B)const{return Cpx(x+B.x,y+B.y);}
    Cpx operator-(const Cpx&B)const{return Cpx(x-B.x,y-B.y);}
    Cpx operator*(const f2&p)const{return Cpx(x*p,y*p);}
    Cpx operator/(const f2&p)const{return Cpx(x/p,y/p);}
    Cpx operator*(const Cpx&B)const{return Cpx(x*B.x-y*B.y,x*B.y-y*B.x);}
    inline void operator=(const f2&p){x=p,y=0;}
    inline void operator+=(const Cpx&B){x+=B.x,y+=B.y;}
    inline void operator-=(const Cpx&B){x-=B.x,y-=B.y;}
    inline void operator*=(const f2&p){x*=p,y*=p;}
    inline void operator/=(const f2&p){x/=p,y/=p;}
    inline void operator*=(const Cpx&B){f2 _x=x*B.x-y*B.y,_y=x*B.y+y*B.x;x=_x,y=_y;}
};
inline void fft(Cpx A[],int n,int rev){
    register int i,j,k;for(i=k=0;i<n;++i){if(i<k)swap(A[i],A[k]);for(j=n>>1;(k^=j)<j;j>>=1);}
    Cpx w,wn,t;
    for(k=2;k<=n;k*=2)
        for(wn=Cpx(cos(2*pi/k),rev*sin(2*pi/k)),i=0;i<n;i+=k)
            for(w=1,j=0;j<k/2;++j,w*=wn)
                t=w,t*=A[i+j+k/2],A[i+j+k/2]=A[i+j]-t,A[i+j]+=t;
    if(rev==-1)for(i=0;i<n;++i)A[i]/=n;
}
  
#define N 100010
  
char s[N],ss[N<<1];
int p[N<<1];
  
Cpx A[262144];
  
int mi[N];
  
int f[N<<1];
int main(){
    scanf("%s",s);
    int len=strlen(s);
      
    register int i;for(mi[0]=1,i=1;i<=len;++i)mi[i]=mi[i-1]*2%mod;
      
    long long res(0);
      
    int l;for(l=1;l<len*2;l<<=1);
    for(i=0;i<len;++i)A[i]=Cpx(s[i]=='a'?1:0,0);fft(A,l,1);for(i=0;i<l;++i)A[i]*=A[i];fft(A,l,-1);
    for(i=0;i<2*len-1;++i)f[i]+=(((int)(A[i].x+0.5))+1)/2;
    for(i=0;i<l;++i)A[i]=Cpx(0,0);
    for(i=0;i<len;++i)A[i]=Cpx(s[i]=='b'?1:0,0);fft(A,l,1);for(i=0;i<l;++i)A[i]*=A[i];fft(A,l,-1);
    for(i=0;i<2*len-1;++i)f[i]+=(((int)(A[i].x+0.5))+1)/2;
    for(i=0;i<2*len-1;++i)res=(res+mi[f[i]]-1)%mod;
    //cout<<res<<endl;
    ss[0]='@',ss[2*len+1]='#',ss[2*len+2]='$';
    for(i=0;i<len;++i)ss[2*i+1]='#',ss[2*i+2]=s[i];len*=2;
    int id(0),mx(0);
    for(i=1;i<=len;++i){
        for(p[i]=i<mx?min(p[2*id-i],mx-i+1):0;ss[i+p[i]]==ss[i-p[i]];++p[i]);
        if(i+p[i]-1>mx)mx=i+p[i]-1,id=i;
    }
    for(i=2;i<=len;++i)res=(res-p[i]/2+mod)%mod;
    cout<<res;
    return 0;
}