https://www.lydsy.com/JudgeOnline/problem.php?id=2179

FFT模板题

1 #include
      
        2 #include
       
         3 #include
        
          4 using namespace std; 5 const int maxn=140005; 6 const double pi=acos(-1); 7 int n,m=1,lg; 8 char s1[maxn],s2[maxn]; 9 int rev[maxn],ans[maxn];10 struct complex{11     double x,y;12     complex(){};13     complex(double xx,double yy){x=xx,y=yy;}14     complex operator+(const complex &a)const{
    return complex(a.x+x,a.y+y);}15     complex operator-(const complex &a)const{
    return complex(x-a.x,y-a.y);}16     complex operator*(const complex &a)const{
    return complex(x*a.x-y*a.y,x*a.y+y*a.x);}17 }a[maxn],b[maxn],c[maxn];18 void FFT(complex *a,int len,int sign){19     for(int i=0;i
         
          
           >1);k++,w=w*wn){25                 complex x=a[j+k],y=w*a[j+(i>>1)+k];26                 a[j+k]=x+y,a[j+k+(i>>1)]=x-y;27             }28         }29     }30     if(sign==-1)for(int i=0;i
           
            >1]>>1)|((i&1)<<(lg-1));40 FFT(a,m,1),FFT(b,m,1);41 for(int i=0;i