bzoj 3160 万径人踪灭 FFT

万径人踪灭

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 1936  Solved: 1076
[Submit][Status][Discuss]

Description

Input

Output

Sample Input

Sample Output

HINT

 

题目大意：给定一个由'a'和'b'构成的字符串，求不连续回文子序列的个数

首先回文一定是将字符串倍增 由于求的是不连续回文子序列的个数 因此我们可以求出总回文子序列的个数，然后减掉连续的

连续的就是回文子串 用Manacher算法可以O(n)求解

不连续的就有些难搞了

首先我们令f[i]表示以i为中心的对称字符对个数

比如s[]=$#a#b#a 那么s[4]='b' f[4]=2

那么对于每个中心i我们有(2^f[i])-1种方案 答案即Σ[1<=i<=n*2+1]((2^f[i])-1)

问题就是如何求出f[]数组

我们发现对f[i]有贡献的一对字符在原字符串数组中的位置之和一定是i

比如str+1="aba" 那么第一个字符和第三个字符对倍增后的字符串的第4个位置有贡献

那么显然有f[i]=(Σ[1<=j<=i-1]bool(str[j]==str[i-j]))+1>>1 括号里面是一个卷积的形式 可以用FFT进行求解

首先考虑'a'对答案的贡献 那么令'a'=1 'b'=0 求出卷积就是'a'的贡献

再考虑'b'对答案的贡献 令'a'=0 'b'=1 求出卷积就是'b'的贡献

两次贡献之和+1>>1就是f[]数组 代入之前的结论中即可出解

 

其中的数值是0和1代入

 

#pragma GCC optimize(2)
#pragma G++ optimize(2)
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<cstdio>

#define mod 1000000007
#define ll long long
#define pi acos(-1)
#define N 300007
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
    return x*f;
}

int n,m,len,L;
ll ans;char ch[N];
int rev[N],bin[N],p[N];
struct comp
{
    double r,v;
    void init(){r=v=0;}
    inline comp operator+(const comp &a){return(comp){r+a.r,v+a.v};}
    inline comp operator-(const comp &a){return(comp){r-a.r,v-a.v};}
    inline comp operator*(const comp &a){return(comp){r*a.r-v*a.v,r*a.v+v*a.r};}
}a[N],f[N],g[N];

void manacher()
{
    ch[0]='+',ch[len+1]='-';
    int id,mx=0;
    for(int i=1;i<=len;i++)
    {
        if(mx>i)p[i]=min(p[2*id-i],mx-i+1);
        else p[i]=1;
        while(ch[i+p[i]]==ch[i-p[i]])p[i]++;
        if(i+p[i]-1>mx)mx=i+p[i]-1,id=i;
        (ans-=p[i])%=mod;
    }
    mx=0;
    for(int i=1;i<=len;i++)
    {
        if(mx>i)p[i]=min(mx-i,p[2*id-i]);
        else p[i]=0;
        while(ch[i+p[i]+1]==ch[i-p[i]])p[i]++;
        if(i+p[i]>mx)mx=i+p[i],id=i;
        (ans-=p[i])%=mod;
    }
}
void FFT(comp *a,int f)
{
    for(int i=0;i<n;i++)if(i<rev[i])swap(a[i],a[rev[i]]);
    for(int i=1;i<n;i<<=1)
    {
        comp wn=(comp){cos(pi/i),f*sin(pi/i)};
        for (int j=0;j<n;j+=(i<<1))
        {
            comp w=(comp){1,0};
            for (int k=0;k<i;k++,w=w*wn)
            {
                comp x=a[j+k],y=w*a[j+k+i];
                a[j+k]=x+y,a[j+k+i]=x-y;
            }
        }
    }
    if(f==-1)for (int i=0;i<n;i++)a[i].r/=n;
}
int main()
{
    bin[0]=1;for (int i=1;i<=100000;i++)bin[i]=(bin[i-1]<<1)%mod;
    scanf("%s",ch+1);len=strlen(ch+1);
    manacher();
    m=2*(len-1);for(n=1;n<=m;n<<=1,L++);if(L)L--;
    for(int i=0;i<n;i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<L);
    for (int i=0;i<len;i++)a[i].r=(ch[i+1]=='a')?1:0;
    FFT(a,1);
    for (int i=0;i<n;i++)f[i]=a[i]*a[i];
    FFT(f,-1);
    for (int i=0;i<n;i++)a[i].init();    
    for (int i=0;i<len;i++)a[i].r=(ch[i+1]=='b')?1:0;
    FFT(a,1);
    for (int i=0;i<n;i++)g[i]=a[i]*a[i];
    FFT(g,-1);
    for (int i=0;i<n;i++)
    {
        int x=(int)(f[i].r+0.5)+(int)(g[i].r+0.5);
        ans+=bin[(x+1)/2]-1;
        ans%=mod;
    }
    printf("%lld",(ans+mod)%mod);
}