快速傅里叶变换

study from：

http://www.cnblogs.com/zwfymqz/p/8244902.html

https://blog.csdn.net/enjoy_pascal/article/details/81478582

luogu3803

https://www.luogu.org/problemnew/show/P3803

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <set>
 6 #include <map>
 7 #include <list>
 8 #include <queue>
 9 #include <vector>
10 #include <bitset>
11 #include <iostream>
12 using namespace std;
13 
14 const int maxn=(1e6+10)*4;///相乘，最多2e6位，同时要加到min 2^k>2e6，乘2即可
15 const double pi=acos(-1);
16 
17 struct Complex
18 {
19     double x,y;
20     ///otherwise create Complex(){}
21     Complex(double xx=0,double yy=0)
22     {
23         x=xx;
24         y=yy;
25     }
26     Complex operator+(const Complex &b) const
27     {
28         return Complex(x+b.x,y+b.y);
29     }
30     Complex operator-(const Complex &b) const
31     {
32         return Complex(x-b.x,y-b.y);
33     }
34     Complex operator*(const Complex &b) const
35     {
36         return Complex(x*b.x-y*b.y,x*b.y+y*b.x);
37     }
38 }a[maxn],b[maxn];
39 
40 int w=0,s,r[maxn];
41 
42 void fft(Complex *a,int inv)
43 {
44     int i,j,m;
45     for (i=0;i<s;i++)
46         if (i<r[i])
47             swap(a[i],a[r[i]]);
48     for (m=1;m<s;m<<=1)
49     {
50         Complex temp(cos(pi/m),inv*sin(pi/m));
51         for (i=0;i<s;i+=m*2)
52         {
53             Complex mul(1,0);
54             for (j=0;j<m;j++,mul=mul*temp)
55             {
56                 Complex x=a[i+j],y=mul*a[i+j+m];
57                 a[i+j]=x+y,a[i+j+m]=x-y;
58             }
59         }
60     }
61 }
62 
63 int main()
64 {
65     int n,m,i;
66     scanf("%d%d",&n,&m);
67     for (i=0;i<=n;i++)
68         scanf("%lf",&a[i].x);
69     for (i=0;i<=m;i++)
70         scanf("%lf",&b[i].x);
71     s=1;
72     while (s<=n+m)  //n+m+1
73         s<<=1,w++;
74     for (i=0;i<s;i++)
75         r[i]=(r[i>>1]>>1) | ((i & 1)<<(w-1));
76     fft(a,1);
77     fft(b,1);
78     for (i=0;i<=s;i++)
79         a[i]=a[i]*b[i];
80     fft(a,-1);
81     for (i=0;i<=n+m;i++)
82         printf("%d ",(int)(a[i].x/s+0.5));
83     return 0;
84 }

NTT
......

FWT

https://www.cnblogs.com/cjyyb/p/9065615.html