【BZOJ 3160】 3160: 万径人踪灭 （FFT）

【分析】

　　看题目被吓死，其实很多废话。。

　　还是自己想出来了。。FFT好强啊。。可以加速很多东西的说。

　　然后就是，枚举对称轴吧？

　　假设a[i]==a[j],那么用i+j表示它的对称轴。

　　共有0~2*n的对称轴，对于每个对称轴它的对称点对个数就是$F[k]=\sum s[k-i]==s[k+i]$

　　注意到只有a和b，假设只考虑a相同，令$a[i]=s[i]=='a'?1:0$

　　那么就是$F[k]=\sum a[k-i]*a[k+i]$

　　化成卷积形式，可以用FFT做了。用b也做一遍

　　最后答案是$\sum 2^{F[k]}$-空串-回文子串（不能连续嘛）

　　回文子串我用马拉车打了，，，然后打错了，，，然后TLE了，，，以为是FFT的递归版太慢，还去学了迭代打法【醉生梦死。。。

 #include<cstdio>

 #include<cstdlib>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 using namespace std;

 #define Maxn 100010*8

 #define Mod 1000000007

 #define LL long long

 const double pi=acos(-);

 int mymin(int x,int y) {return x<y?x:y;}

 struct P

 {

     double x,y;

     P() {x=y=;}

     P(double x,double y):x(x),y(y){}

     friend P operator + (P x,P y) {return P(x.x+y.x,x.y+y.y);}

     friend P operator - (P x,P y) {return P(x.x-y.x,x.y-y.y);}

     friend P operator * (P x,P y) {return P(x.x*y.x-x.y*y.y,x.x*y.y+x.y*y.x);}

 }a[Maxn];

 int i,j,k;

 int nn=,R[Maxn];

 void fft(P *a,int f)

 {

     for(i=;i<nn;i++) if(i<R[i]) swap(a[i],a[R[i]]);

     for(i=;i<nn;i<<=)

     {

         P wn(cos(pi/i),f*sin(pi/i));

         for(int ad=i<<,j=;j<nn;j+=ad)

         {

             P w(,);

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

             {

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

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

             }

         }

     }

 }

 char s[Maxn];

 int ans[Maxn];

 int aa[Maxn],pp[Maxn];

 int get_manacher(int ll)

 {

     int mx=,id=;

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

     {

         int k;

         if(i<mx) k=mymin(pp[*id-i],mx-i+);

         else k=;

         while(aa[i+k]==aa[i-k]&&i-k>=&&i+k<=ll) k++;

         pp[i]=k;

         if(i+pp[i]->mx) mx=i+pp[i]-,id=i;

     }

     int as=;

     for(int i=;i<=ll;i+=) as=(as+(pp[i]+)/)%Mod;

     for(int i=;i<=ll;i+=) as=(as+pp[i]/)%Mod;

     return as;

 }

 int bin[Maxn];

 int main()

 {

     scanf("%s",s);

     int n=strlen(s);n--;

     for(i=;i<=n;i++) a[i].x=(s[i]=='a'?:);

     int ll=;nn=;

     while(nn<=n+n) ll++,nn<<=;

     for(i=;i<nn;i++) R[i]=(R[i>>]>>)|((i&)<<(ll-));

     fft(a,);for(i=;i<=nn;i++) a[i]=a[i]*a[i];fft(a,-);

     for(i=;i<=n+n;i++) ans[i]=(int)(a[i].x/nn+0.5);

     for(i=;i<=nn;i++) a[i].x=a[i].y=;

     for(i=;i<=n;i++) a[i].x=(s[i]=='a'?:),a[i].y=;

     fft(a,);for(i=;i<=nn;i++) a[i]=a[i]*a[i];fft(a,-);

     for(i=;i<=n+n;i++) ans[i]+=(int)(a[i].x/nn+0.5);

     for(i=;i<=n+n;i++) ans[i]=(ans[i]+)/;

     int a1=;

     bin[]=;for(i=;i<=n;i++) bin[i]=(bin[i-]*)%Mod;

     for(i=;i<=n+n;i++) a1=(a1+bin[ans[i]])%Mod;

     a1-=n+n+;

     aa[]=;for(int i=;i<=n;i++) aa[*i+]=s[i]-'a',aa[*i+]=;aa[*n+]=;

     a1-=get_manacher(*n+);

     a1=(a1%Mod+Mod)%Mod;

     printf("%d\n",a1);

     return ;

 }

【所以我现在会迭代打法了hhh

2017-04-13 18:42:35