zcmimi's blog
avatar
zc
2020-07-05 13:10:00
  • 本文总阅读量
查看原题

点击跳转

首先找位置对称的回文子序列个数(多项式求)

由于不能连续,所以减去对称回文子串个数(manacher求)

设字符串为S,|S|=n

假设S_i作为一个子序列的对称中心,x=\sum_{j=1\le j\le i-1}[S_{i-j}=S_{i+j}]

那么以i为中心位置的方案数为2^{x+1}-1

A_i=[S_i=a],B_i=[S_i=b]

那么\displaystyle (A*A)_i=A_i*A_i=\sum_{j=0}^nA_jA_{i-j}就是对称中心为位置\frac i2的两端为a的数量

同理(B*B)_i就是对称中心为位置\frac i2的两端为b的数量

那么上述(A*A)_i+(B*B)_i就是对称中心为位置\frac i2x+1

如果i为偶数,x+1要减去1(对称中心是否在同个字符上)

#include<bits/stdc++.h>
const int N=100011,P=1000000007;
typedef double db;
typedef long long ll;
struct cp{db r,i;cp(db R=0,db I=0){r=R,i=I;}};
cp operator+(cp a,cp b){return cp(a.r+b.r,a.i+b.i);}
cp operator-(cp a,cp b){return cp(a.r-b.r,a.i-b.i);}
cp operator*(cp a,cp b){return cp(a.r*b.r-a.i*b.i,a.r*b.i+a.i*b.r);}
char s[N],S[N*2];
int n,nn,ans,pw[N],l,r[N*4],p[N*2];
const db pi=acos(-1);
cp a[N*4],b[N*4];
void swap(cp&x,cp&y){cp t=x;x=y;y=t;}
void fft(cp*A,int typ){
    for(int i=0;i<nn;++i)
        if(i<r[i])swap(A[i],A[r[i]]);
    for(int len=1;len<nn;len<<=1){
        cp Wn(cos(pi/len),typ*sin(pi/len));
        for(int i=0;i<nn;i+=len<<1){
            cp w(1,0);
            for(int k=0;k<len;++k){
                cp t=w*A[i+k+len];
                A[i+k+len]=A[i+k]-t;
                A[i+k]=A[i+k]+t;
                w=w*Wn;
            }
        }
    }
}
void mod(int&x){if(x>=P)x-=P;}
int min(int x,int y){return x<y?x:y;}
int main(){
    scanf("%s",s+1);
    n=strlen(s+1);
    pw[0]=1;
    for(int i=1;i<=n;++i)
        a[i].r=s[i]=='a',
        b[i].r=s[i]=='b',
        mod(pw[i]=pw[i-1]<<1);
    for(nn=1;nn<=n+n;nn<<=1,++l);
    for(int i=0;i<nn;++i)
        r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    fft(a,1),fft(b,1);
    for(int i=0;i<nn;++i)
        a[i]=a[i]*a[i],
        b[i]=b[i]*b[i];
    fft(a,-1),fft(b,-1);

    n=n<<1|1;
    for(int i=1;i<=n;++i)
        S[i]=(i&1)?'#':s[i>>1];
    int R=0,m=0;
    for(int i=1;i<=n;++i){
        if(i<=R)p[i]=min(R-i,p[m*2-i]);
        while(i+p[i]+1<=n&&i-p[i]-1>=1&&S[i+p[i]+1]==S[i-p[i]-1])++p[i];
        if(i+p[i]>R)R=i+p[i],m=i;
    }
    for(int i=1;i<=n;++i)mod(ans+=P-(p[i]+1>>1));

    for(int i=1;i<=n;++i){
        int x=int(a[i].r/nn+0.5)%P+int(b[i].r/nn+0.5)%P+1;
        x>>=1;
        mod(x);
        mod(ans+=pw[x]-1);
    }
    printf("%d\n",ans);
}
LG 4199 万径人踪灭
comment评论
Search
search