woc......FFT这玩意儿真坑......
一上午除了打了几遍板子什么也没干......真是废了......
你要加油啊......
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=;
const double pi=acos(-1.0),eps=1e-;
struct Complex{
double a,b;
Complex(double a=0.0,double b=0.0):a(a),b(b){}
Complex operator+(const Complex &x)const{return Complex(a+x.a,b+x.b);}
Complex operator-(const Complex &x)const{return Complex(a-x.a,b-x.b);}
Complex operator*(const Complex &x)const{return Complex(a*x.a-b*x.b,a*x.b+b*x.a);}
}A[maxn],B[maxn];
void FFT(Complex*,int,int);
int n,m,N=;
int main(){
scanf("%d%d",&n,&m);
n++;m++;
while(N<n+m)N<<=;
for(int i=;i<n;i++)scanf("%lf",&A[i].a);
for(int i=;i<m;i++)scanf("%lf",&B[i].a);
FFT(A,N,);
FFT(B,N,);
for(int i=;i<N;i++)A[i]=A[i]*B[i];
FFT(A,N,-);
for(int i=;i<n+m-;i++)printf("%d ",(int)(A[i].a+eps));
return ;
}
void FFT(Complex *A,int n,int tp){
for(int i=,j=;i<n-;i++){
int k=N;
do{
k>>=;
j^=k;
}while(j<k);
if(i<j)swap(A[i],A[j]);
}
for(int k=;k<=n;k<<=){
Complex wn(cos(-tp**pi/k),sin(-tp**pi/k));
for(int i=;i<n;i+=k){
Complex w(1.0,0.0);
for(int j=;j<(k>>);j++,w=w*wn){
Complex a(A[i+j]),b(w*A[i+j+(k>>)]);
A[i+j]=a+b;
A[i+j+(k>>)]=a-b;
}
}
}
if(tp<)for(int i=;i<n;i++)A[i].a/=n;
}
挖个大坑：