[模板]FFT
aRenBigFather
2019-04-01 19:40:19
```cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10000010;
const double PI = acos(-1.0);
struct Complex{
double xx,yy;
Complex(){}
Complex(double _xx,double _yy){
xx = _xx;
yy = _yy;
}
};
Complex operator + (const Complex &a,const Complex &b){
return Complex(a.xx+b.xx,a.yy+b.yy);
}
Complex operator - (const Complex &a,const Complex &b){
return Complex(a.xx-b.xx,a.yy-b.yy);
}
Complex operator * (const Complex &a,const Complex &b){
return Complex(a.xx*b.xx-a.yy*b.yy,a.xx*b.yy+a.yy*b.xx);
}
int lim = 1;
int l=0,r[maxn];
Complex a[maxn],b[maxn];
void FFT(Complex *A,int type){
for(int i=0;i<lim;i++){
if(i < r[i]) swap(A[i],A[r[i]]);
}
for(int mid = 1;mid<lim;mid<<=1){
Complex Wn(cos(PI/mid),type*sin(PI/mid));
//单位根
for(int R=mid<<1,j=0;j<lim;j+=R){
Complex w(1,0);
for(int k=0;k<mid;k++,w=w * Wn)
{
Complex x = A[j+k];
Complex y = w * A[j+mid+k];
A[j + k] = x + y;
A[j + mid + k] = x - y;
}
}
}
}
int n,m;
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++) {
int tmp;
scanf("%d",&tmp);
a[i].xx = tmp;
}
for(int i=0;i<=m;i++) {
int tmp;
scanf("%d",&tmp);
b[i].xx = tmp;
}
while(lim <= n+m){
lim <<= 1;
l++;
}
for(int i=0;i<lim;i++){
r[i] = (r[i>>1] >> 1) | ((i & 1) << (l-1));
//printf("r[%d]=%d\n",i,r[i]);
}
//printf("l:%d lim:%d\n",l,lim);
FFT(a,1);
FFT(b,1);
for(int i=0;i<=lim;i++) a[i] = a[i] * b[i];
FFT(a,-1);
for(int i=0;i<=n+m;i++){
printf("%d ",(int)(a[i].xx / lim + 0.5));
}
return 0;
}
```