【BZOJ3160】万径人踪灭（FFT，manacher）-白红宇

【BZOJ3160】万径人踪灭（FFT，manacher）

阅读量：6679 次

发布时间：2019-06-25

本文共 1557 字，大约阅读时间需要 5 分钟。

前言

多项式真的很难♂啊qwq

Solution

考虑求的是一个有间隔的回文串，相当于是：

总的答案-没有间隔的答案

考虑总的答案怎么计算？FFT卷一下就好了。

对于每一位字符，有两种取值，然后随便卷起来，卷起来就是当前这一位之前与它相同的字符个数（这一位不能是‘0’，也就是被排斥的那一位）

然后就可以轻松解决？

是的。

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define ll long long#define re registerusing namespace std;inline int gi(){ int f=1,sum=0;char ch=getchar(); while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0' && ch<='9'){sum=(sum<<3)+(sum<<1)+ch-'0';ch=getchar();} return f*sum;}const int maxn=2000010,Mod=1e9+7;const double Pi=acos(-1.0);char s[maxn];int len,N,M,p[maxn],r[maxn];ll f[maxn],tw[maxn],ans;complex
            
             a[maxn],b[maxn];ll manacher(){ s[len+len+1]='#';s[0]=' '; for(int i=len;i;i--){ s[i*2]=s[i];s[i*2-1]='#'; } int mx=0,id=0; for(int i=1;i<=len+len;i++){ p[i]=mx>i?min(p[id*2-i],mx-i):1; while(s[p[i]+i]==s[i-p[i]])p[i]++; if(i+p[i]>mx){ id=i;mx=i+p[i]; } } ll ret=0; for(int i=1;i<=len+len;i++) ret=(ret+p[i]/2)%Mod; return ret;}void FFT(complex
             
               *P,int opt){ for(int i=0;i
              
               
                 W(cos(Pi/i),opt*sin(Pi/i)); for(int p=i<<1,j=0;j
                
                  w(1,0); for(int k=0;k
                 
                   X=P[j+k],Y=P[i+j+k]*w;; P[j+k]=X+Y;P[i+j+k]=X-Y; } } }}void work(char cc){ memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); for(int i=1;i<=len;++i)a[i]=b[i]=s[i]==cc; FFT(a,1);FFT(b,1); for(int i=0;i
                  
                   >1]>>1)|((i&1)<<(l-1)); work('a');work('b'); for(int i=1;i<=M;i++)ans=(ans+tw[f[i]]-1)%Mod; printf("%lld\n",(ans-manacher()+Mod)%Mod); return 0;}