【bzoj3160】万径人踪灭 FFT

时间：2024-06-06 13:05:14

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3160

我是一个傻叉 微笑脸

 #include<bits/stdc++.h>

 #define inf 1000000000

 #define ll long long

 #define N 200005

 #define mod 1000000007

 using namespace std;

 int read(){

   int x=,f=;char ch=getchar();

   while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

   while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

   return x*f;

 }

 struct CD{

   double x,y;

   CD(double a=,double b=){x=a;y=b;}

   friend CD operator + (CD n1,CD n2){return CD(n1.x+n2.x,n1.y+n2.y);}

   friend CD operator - (CD n1,CD n2){return CD(n1.x-n2.x,n1.y-n2.y);}

   friend CD operator * (CD n1,CD n2){return CD(n1.x*n2.x-n1.y*n2.y,n1.x*n2.y+n1.y*n2.x);}

 };

 const double Pi=acos(-1.0);

 int bit,n,nn,ans,m,mx,id,p[N<<];

 char s[N],st[N<<];

 CD a[N<<],b[N<<];

 void FFT(CD *a,int n,int type){

   for(int i=,j=;i<n;i++) {

     if(j>i)swap(a[i],a[j]);

     int k=n;

     while(j&(k >>= ))j&=~k;

     j|=k;

   }

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

     CD w_n(cos(*type*Pi/(<<i)),sin(*type*Pi/(<<i)));

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

       CD w(,);

       for(int k=j;k<j+(<<(i-));k++){

         CD tmp=a[k],tt=w*a[k+(<<(i-))];

         a[k]=tmp+tt;

         a[k+(<<(i-))]=tmp-tt;

         w=w*w_n;

       }

     }

   }

   if(type<)for(int i=;i<n;i++)a[i].x/=n;

 }

 int main(){

   scanf("%s",s);

   n=strlen(s);nn=n;

   bit=;

   while((<<bit)<(n<<))bit++;

   n=<<bit;

   for(int i=nn;i<n;i++)a[i]=b[i]=CD(,);

   for(int i=;i<nn;i++)if(s[i]=='a')a[i]=CD(,);

   FFT(a,n,);

   for(int i=;i<n;i++)a[i]=a[i]*a[i];

   FFT(a,n,-);

   for(int i=;i<nn;i++)if(s[i]=='b')b[i]=CD(,);

   FFT(b,n,);

   for(int i=;i<n;i++)b[i]=b[i]*b[i];

   FFT(b,n,-);

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

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

     x=(x+)/;

     ans=(ans+(<<x)-)%mod;

   }

   m=nn<<|;

   for(int i=;i<nn;i++)st[(i+)<<]=s[i];

   mx=id=;

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

     if(mx>i)p[i]=min(p[*id-i],mx-i);else p[i]=;

     while(i-p[i]->&&i+p[i]+<=m&&st[i-p[i]-]==st[i+p[i]+])p[i]++;

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

     ans=((ans-(p[i]+)/)%mod+mod)%mod;

   }

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

   return ;

 }

相关文章