bzoj 3160: 万径人踪灭 manachar + FFT

3160: 万径人踪灭

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 133  Solved: 80
[Submit][Status][Discuss]

Description

Input

Output

 

Sample Input

 

Sample Output

 

HINT

　　以每一个位置为中心，分别处理连续一块的回文串，回文序列个数。

　　比较容易看出是FFT+manachar，但是FFT还是不太熟悉，特别要注意三层for语句中i,j,k不能写错，这东西很难调试出来。

　　另外一点就是manachar加‘#’最好头尾都加，要不然第一个，最后一个字符回文串长度会出问题。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define MAXN 610000
#define MOD 1000000007
typedef long long qword;
typedef double real;
const real pi=acos(-1);
struct Complex
{
        real x,y;
        Complex(real x,real y=0):x(x),y(y){}
        Complex(){}
};
Complex operator +(Complex c1,Complex c2)
{
        return Complex(c1.x+c2.x,c1.y+c2.y);
}
Complex operator -(Complex c1,Complex c2)
{
        return Complex(c1.x-c2.x,c1.y-c2.y);
}
Complex operator *(Complex c1,Complex c2)
{
        return Complex(c1.x*c2.x-c1.y*c2.y,c1.x*c2.y+c1.y*c2.x);
}
Complex operator /(Complex c1,real x)
{
        return Complex(c1.x/x,c1.y/x);
}
Complex g1[MAXN],g2[MAXN],g3[MAXN];
Complex gt[MAXN];
void FFT(Complex gg[],int l,int pp)
{
        memcpy(gt,gg,sizeof(gt[0])*l);
        int x;
        for (int i=0;i<l;i++)
        {
                x=0;
                for (int j=1,k=l>>1;j<l;j<<=1,k>>=1)
                        if (i&j)x+=k;
                gg[i]=gt[x];
        }
        Complex w;
        Complex wn;
        Complex tmp;
        for (int i=1;i<l;i<<=1)
        {
                wn=Complex(cos(pi/i*pp),sin(pi/i*pp));
                for (int j=0;j<l;j+=(i<<1))
                {
                        w=Complex(1,0);
                        for (int k=0;k<i;k++)
                        {
                                tmp=gg[j+k];
                                gg[j+k]=gg[j+k]+gg[i+j+k]*w;
                                gg[i+j+k]=tmp-w*gg[i+j+k];
                                w=w*wn;
                        }
                }
        }
}
qword pow_mod(qword x,qword y)
{
        qword ret=1;
        while (y)
        {
                if (y&1)ret=ret*x%MOD;
                x=x*x%MOD;
                y>>=1;
        }
        return ret;
}
char str[MAXN];
char str2[MAXN];
int plen[MAXN];
int plen2[MAXN];
void manachar(int l)
{
        int id=-1,mx=0;
        for (int i=0;i<l;i++)
        {
                if (mx>i)
                        plen[i]=min(mx-i,plen[id*2-i]);
                while (i-plen[i]-1>=0 && i+plen[i]+1<l && str2[i-plen[i]-1]==str2[i+plen[i]+1])
                        plen[i]++;
                if (i+plen[i]>mx)
                {
                        mx=i+plen[i];
                        id=i;
                }
        }
}
qword mi2[MAXN];
int main()
{
        freopen("input.txt","r",stdin);
        int n,m;
        int x,y;
        int l;
        scanf("%s",str);
        n=strlen(str);
        l=n*2+1;
        mi2[0]=1;
        for (int i=1;i<=l;i++)mi2[i]=mi2[i-1]*2%MOD;
        for (int i=0;i<n*2+1;i++)
                str2[i]='#';
        for (int i=0;i<n;i++)
        {
                if (str[i]=='a')
                {
                        g1[i*2+1]=g2[i*2+1]=1;
                        str2[i*2+1]='a';
                }else
                {
                        g1[i*2+1]=g2[i*2+1]=-1;
                        str2[i*2+1]='b';
                }
        }
        manachar(l);
        for (l=n*2;l!=(l&(-l));l-=l&(-l));
        l<<=2;
        FFT(g1,l,1);
        FFT(g2,l,1);
        for (int i=0;i<l;i++)g3[i]=g1[i]*g2[i];
        FFT(g3,l,-1);
        for (int i=0;i<l;i++)g3[i]=g3[i]/l;
        l=n*2;
        for (int i=0;i<l;i++)plen[i]++;
        qword ans=0;
        for (int i=0;i<l;i++)
                plen2[i]=((min(i,l-i-1)+1)+round(g3[i*2].x))/2;
        for (int i=0;i<l;i++)plen2[i]=(plen2[i]+1)/2;
        for (int i=0;i<l;i++)plen[i]=plen[i]/2;
        for (int i=0;i<l;i++)
                ans=(ans+mi2[plen2[i]]-1-plen[i])%MOD;
        printf("%lld
",ans);
        return 0;
}