bzoj千题计划256：bzoj2194: 快速傅立叶之二-白红宇

bzoj千题计划256：bzoj2194: 快速傅立叶之二

阅读量：5255 次

发布时间：2019-06-14

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

相乘两项的下标的差相同

那么把某一个反过来就是卷积形式

fft优化

#include
     
      #include
      
       #include
       
        #include
        
         using namespace std;const int N=(1<<18)+2;const double pi=acos(-1);int r[N];struct Complex{    double a,b;    Complex(double x_=0,double y_=0):a(x_),b(y_) {}    Complex operator + (Complex p)    {        Complex c;        c.a=a+p.a;        c.b=b+p.b;        return c;    }        Complex operator - (Complex p)    {        Complex c;        c.a=a-p.a;        c.b=b-p.b;        return c;    }    Complex operator * (Complex p)    {        Complex c;        c.a=a*p.a-b*p.b;        c.b=a*p.b+b*p.a;        return c;    }};typedef Complex E;E A[N],B[N],C[N];int n;void read(int &x){    x=0; char c=getchar();    while(!isdigit(c)) c=getchar();    while(isdigit(c)) { x=x*10+c-'0'; c=getchar(); }}void fft(E *a,int f){    for(int i=0;i
         
          >1]>>1)|((i&1)<
          
           =0;--i) printf("%d\n",int(C[i].a/n+0.5));}