简述:OI中的 快速傅里叶变换(Fast Fourier Transform,FFT)

Menci-FFT学习笔记


板子

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
// luogu-judger-enable-o2
#include <cstdio>
#include <cmath>
#include <cctype>
#include <memory>
#define re register int
const int N=2621450;
const double pi=acos(-1);
struct cpx{
double r,i;
cpx(){}
cpx(double _r,double _i){r=_r, i=_i;}
inline cpx operator * (const cpx& rhy)const{
return cpx(r*rhy.r - i*rhy.i, r*rhy.i + i*rhy.r);
}
inline cpx operator *= (const cpx& rhy){
*this = *this * rhy;
}
inline cpx operator + (const cpx& rhy)const{
return cpx(r+rhy.r, i+rhy.i);
}
inline cpx operator - (const cpx& rhy)const{
return cpx(r-rhy.r, i-rhy.i);
}
}a[N],b[N]; //complex

inline void read(int &x){
x=0;
int f=1;char ch=getchar();
while (!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while (isdigit(ch)){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
x*=f;
}

int n, m, ans[N], R[N];
inline void FFT(int n, cpx *a, int f){
for(re i = 0 ; i < n ; ++i)
if(R[i] > i) std::swap(a[R[i]], a[i]); //二进制翻转

for(re l = 1 ; l < n ; l<<=1) {
cpx wn(cos(pi/l), f*sin(pi/l));
for(re j = 0 ; j < n ; j += (l<<1)) {
cpx omega(1.0, 0.0);
for(re k = 0 ; k < l ; ++k,omega*=wn) {
cpx t = omega * a[j+k+l];
a[j+k+l] = a[j+k] - t;
a[j+k] = a[j+k] + t;
}
}
} // 分治+蝴蝶变换

if(f == -1)
for(re i = 0 ; i < n ; ++i) a[i].r /= n; //系数转换
}

int main(int argc,char *argv[]){
read(n), read(m);
int x;
for(re i = n ; i >= 0 ; --i) read(x), a[i].r=x;
for(re i = m ; i >= 0 ; --i) read(x), b[i].r=x;
int _n=1;
while(_n <= n+m) _n<<=1;
for(re i = 0 ; i < _n ; ++i)
R[i]=( (R[i>>1]>>1) | (_n>>(i&1)) ) & (_n-1); //二进制反转预处理

FFT(_n, a, 1), FFT(_n, b, 1);
for(re i = 0 ; i <= _n ; ++i) a[i]*=b[i]; //点值转换
FFT(_n, a, -1);

for(re i = 0 ; i<=n+m ; ++i) ans[i]=a[i].r + 0.5;
for(re i = n+m ; i>=0 ; --i) printf("%d ", ans[i]);
}