都说这是个FFT模板题 可我这种蒟蒻还是看了大半天。。。

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 #include
           
             8 #include
            
              9 #include
             
              10 #define M 100000911 #define EPS 1e-1012 #define MO 1000013 #define ll long long14 #define E complex
              
               15 #define pi acos(-1)16 using namespace std;17 ll read()18 {19 char ch=getchar();20 ll x=0,f=1;21 for(;ch<'0'||ch>'9';ch=getchar())22 if(ch=='-')23 f=-1;24 for(;ch>='0'&&ch<='9';ch=getchar())25 x=x*10+ch-'0';26 return x*f;27 }28 E g[M],f[M],_f[M];29 int n,L,R[M];30 void fft(E a[M],int f)31 {32 for(int i=0;i
               
                R[i])34 swap(a[i],a[R[i]]);35 for(int i=1;i
                
                 <<=1)36 {37 E wn(cos(pi/i),f*sin(pi/i));38 for(int j=0;j
                 
                  <<1))39 {40 E W(1,0);41 for(int k=0;k
                  
                   >1]>>1)|((i&1)<<(L-1));71 fft(f,1);72 fft(_f,1);73 fft(g,1);74 for(int i=0;i