BZOJ 3160: 万径人踪灭

略。见 BZOJ3160

Solution

对于“不能是连续的一段”，可以先计算所有答案，然后减去连续一段的，即回文串，这个用回文自动机或者 manacher 可以得出。
考虑以每个位置为中心的对称元素对个数 $f_i$，那么 i 位置对答案的贡献是 $2^{f_i}-1$。
如果把 a 视为 1，b 视为-1，然后把原串长度 $\times 4$，卷积，那么以 i 为中心的元素对如果相同，则贡献 1，否则贡献 -1。

Code

#include<bits/stdc++.h>
typedef double lf;

#define fo0(i,n) for(int i=0,i##end=n;i<i##end;i++)
#define fo1(i,n) for(int i=1,i##end=n;i<=i##end;i++)

inline int mod(int x,int y){if(x>=y)return x-y;return x;}

#define N 524288

struct num
{
    lf r,i;
    num(){r=i=0;}
    num(lf x){r=x,i=0;}
    num(lf x,lf y){r=x,i=y;}
    num(const num &x){r=x.r,i=x.i;}
    inline num& operator +=(const num &x){r+=x.r,i+=x.i;}
    inline num& operator -=(const num &x){r-=x.r,i-=x.i;}
    inline num& operator *=(const num &x){lf a=r*x.r-i*x.i,b=r*x.i+i*x.r;r=a,i=b;}
    inline num operator +(const num &x){num t=*this;t+=x;return t;}
    inline num operator -(const num &x){num t=*this;t-=x;return t;}
    inline num operator *(const num &x){num t=*this;t*=x;return t;}
};

int id[N];
num tx[N],mf[N];

inline void init_id(int y)
{
    fo0(i,1<<y)id[i]=id[i>>1]>>1|(i&1)<<y-1;
}

#define idft(a,b) dft(a,b,1)

inline void dft(num *s,int n,bool II=0)
{
    fo0(i,1<<n)tx[i]=s[id[i]];
    fo1(p,n)
    {
        lf tmp=M_PI*2/(1<<p);
        if(II)tmp=-tmp;
        num t0(1),t1(cos(tmp),sin(tmp));
        fo0(i,1<<p-1)mf[i]=t0,t0*=t1;
        num X,Y;
        for(int i=0,ie=1<<p,ir=ie/2,pp=ir-1;i<(1<<n);i+=ie)fo0(j,ir)
        {
            X=tx[i|j],Y=tx[i|j|ir]*mf[j];
            tx[i|j]=X+Y,tx[i|j|ir]=X-Y;
        }
    }
    fo0(i,1<<n)s[i]=tx[i];
}

#define N2 100010

struct node
{
    int len,cnt;
    node *nxt[2],*fail;
}t[N2+2],*tm=t+2;

inline void build(char *s,int n)
{
    t[0].len=0,t[1].len=-1;
    node *cur=t+1,*tmp,*t2;
    t[0].fail=t+1;
    for(int i=0;i<n;i++)
    {
        char u=s[i]-'a';
        for(;s[i]!=s[i-1-cur->len];cur=cur->fail);
        if(cur->nxt[u])
            cur=cur->nxt[u],cur->cnt++;
        else
        {
            tmp=cur->nxt[u]=tm++;
            tmp->len=cur->len+2;
            tmp->cnt=1;
            if(tmp->len==1)
                tmp->fail=t;
            else
            {
                for(t2=cur->fail;s[i]!=s[i-1-t2->len];t2=t2->fail);
                tmp->fail=t2->nxt[u];
            }
            cur=tmp;
        }
    }
}

inline void count()
{
    for(node *x=tm-1;x>=t;x--)
        if(x->fail)x->fail->cnt+=x->cnt;
}

#define P 1000000007

inline int cnt()
{
    int ans=0;
    for(node *x=tm-1;x>t+1;x--)
        ans=mod(ans+x->cnt,P);
    return ans;
}

char s[100000];
num p[N];
int po[100001];

int main()
{
    scanf("%s",s);
    int n=strlen(s);
    fo1(i,n/2+5)po[i]=mod(mod(po[i-1]*2+1,P),P);
    int y=0;
    while((1<<(y+1))<n*4)y++;y++;
    fo0(i,n)p[i]=s[i]=='a'?1:-1;
    init_id(y);
    dft(p,y);
    fo0(i,1<<y)p[i]*=p[i];
    idft(p,y);
    lf t=1.0/(1<<y);
    int ans=0;
    fo0(i,n*2-1)
    {
        int cnt=round(p[i].r*t);
        cnt=(std::min(i/2+1,(n*2-i)/2)+(cnt&1?(cnt+1)/2:cnt/2))/2;
        ans=mod(ans+po[cnt],P);
    }
    build(s,n);
    count();
    printf("%d",mod(ans+P-cnt(),P));
}

日期： 2017-01-20

标签： BZOJ 回文自动机 FFT

这是一篇旧文，原始文章及评论可在 https://oldblog.mcfx.us/archives/175/ 查看。