BZOJ3160:万径人踪灭(FFT,Manacher)

Solution

$ans=$回文子序列$-$回文子串的数目。

后者可以用$manacher$直接求。

前者设$f[i]$表示以$i$为中心的对称的字母对数。

那么回文子序列的数量也就是$\sum_{i=0}^{n-1}2^{f[i]-1}$

构造两个数组$a[i],b[i]$。若第$i$位为$a$，那么$a[i]=1$，否则$b[i]=1$。

可以发现$a$数组自身卷积就是$a$字母对$f$数组的贡献，$b$数组同理。

卷下$a$，卷下$b$，对应位置求和，就是$f$数组。

因为在卷积中每对对称字符被算了两次，而自己和自己关于自己对称只算了一次，所以要把答案除2向上取整。

Code

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #include<cmath>

 #define N (400009)

 #define LL long long

 #define MOD (1000000007)

 using namespace std;

 int n,fn,l,tot,r[N],len[N],p[N];

 LL Re,fun;

 char s[N],st[N];

 double pi=acos(-1.0);

 struct complex

 {

     double x,y;

     complex (double xx=,double yy=)

     {

         x=xx; y=yy;

     }

 }a[N],b[N];

 complex operator + (complex a,complex b) {return complex(a.x+b.x,a.y+b.y);}

 complex operator - (complex a,complex b) {return complex(a.x-b.x,a.y-b.y);}

 complex operator * (complex a,complex b) {return complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}

 complex operator / (complex a,double b) {return complex(a.x/b,a.y/b);}

 void FFT(int n,complex *a,int opt)

 {

     for (int i=; i<n; ++i)

         if (i<r[i]) swap(a[i],a[r[i]]);

     for (int k=; k<n; k<<=)

     {

         complex wn=complex(cos(pi/k),opt*sin(pi/k));

         for (int i=; i<n; i+=k<<)

         {

             complex w=complex(,);

             for (int j=; j<k; ++j,w=w*wn)

             {

                 complex x=a[i+j], y=w*a[i+j+k];

                 a[i+j]=x+y; a[i+j+k]=x-y;

             }

         }

     }

     if (opt==-) for (int i=; i<n; ++i) a[i]=a[i]/n;

 }

 void Manacher()

 {

     s[++tot]='('; s[++tot]='#';

     for (int i=; i<n; ++i)

         s[++tot]=st[i], s[++tot]='#';

     s[++tot]=')';

     int maxn=,mid=,x;

     for (int i=; i<=tot; ++i)

     {

         if (i>maxn) x=;

         else x=min(maxn-i+,len[mid*-i]);

         while (s[i+x]==s[i-x]) x++;

         len[i]=x;

         if (i+x->maxn) maxn=i+x-, mid=i;

         fun=(fun+len[i]/)%MOD;

     }

 }

 int main()

 {

     p[]=;

     for (int i=; i<=; ++i)

         p[i]=p[i-]*%MOD;

     scanf("%s",st);    n=strlen(st);

     Manacher();

     fn=;

     while (fn<=n+n) fn<<=, l++;

     for (int i=; i<fn; ++i)

         r[i]=(r[i>>]>>) | ((i&)<<(l-));

     for (int i=; i<n; ++i)

         if (st[i]=='a') a[i].x=;

         else b[i].x=;

     FFT(fn,a,); FFT(fn,b,);

     for (int i=; i<fn; ++i)

         a[i]=a[i]*a[i], b[i]=b[i]*b[i];

     FFT(fn,a,-); FFT(fn,b,-);

     for (int i=; i<fn; ++i)

     {

         int x=(a[i].x+b[i].x+0.5);

         x=(x+)>>;

         Re=(Re+p[x]-)%MOD;

     }

     printf("%lld\n",(Re-fun+MOD)%MOD);

 }

巴特西

BZOJ3160:万径人踪灭(FFT,Manacher)

Solution

Code

最新文章

热门文章