FFT,最后两个点一直是WA的,能不能帮我看看??
#include<cmath>
#include<math.h>
#include<cstdio>
#include<complex>
#include<iostream>
#include<algorithm>
#define PI M_PI
#define N 1000005
using namespace std;
int n,m1,m2;
int rev[N];
complex<double>A[N],B[N];
void FFT(complex<double> *A, int type) {
for (int i=0;i<n;++i)
if (i<rev[i]) swap(A[i],A[rev[i]]);
for (int j=1;j<n;j<<=1){
complex<double>W(cos(PI/j),sin(PI/j)*type);
for (int k=0;k<n;k+=(j<<1)){
complex<double>w(1.0,0.0);
for (int i=0;i<j;++i){
complex<double>ye,yo;
ye=A[i+k];yo=A[i+j+k]*w;
A[i+k]=ye+yo;
A[i+j+k]=ye-yo;
w*=W;
}
}
}
return;
}
int main(){
scanf("%d%d",&m1,&m2);
for (int i=0;i<=m1;++i) cin>>A[i];
for (int i=0;i<=m2;++i) cin>>B[i];
n=m1+m2;
for (int i=1;i<=20;++i) if ((1<<i)>n){
n=1<<i;
break;
}
for (int i=0;i<n;++i)
rev[i]=(rev[i>>1]>>1)|((i&1)?(n>>1):0);
FFT(A,1);FFT(B,1);
for (int i=0;i<=n;++i)
A[i]*=B[i];
FFT(A,-1);
for (int i=0;i<=m1+m2;++i)
printf("%d ",(int)(A[i].real()/(double)n+0.5));
return 0;
}