非递归 fft33pts求调 没过样例

#include<bits/stdc++.h>
#define MAXN 4000010
using namespace std;
const int N=4e6+6,PI=acos(1.0);
int n,m,rev[N];
struct fs{
	double real,imag;
	fs(){real=imag=0.0;}
	fs(double x){real=x,imag=0.0;}
	fs(double x,double y){real=x,imag=y;}
	fs operator+(fs a)const{
		return fs(real+a.real,imag+a.imag);
	}
	fs operator-(fs a)const{
		return fs(real-a.real,imag-a.imag);
	}
	fs operator*(fs a)const{
		return fs(real*a.real-imag*a.imag,real*a.imag+imag*a.real);
	}
	inline void operator/=(double x){
		real/=x,imag/=x;
	}
}A[N],B[N],u[N];
inline void FFT(fs *A,int size,bool flag){
	rev[0]=0;
	for(int i=1;i<size;i++){
		rev[i]=rev[i>>1]>>1;
		if(i&1)rev[i]|=(size>>1);
	}
	for(int i=0;i<size;i++)if(rev[i]>i)swap(A[i],A[rev[i]]);
	double ang=(flag?2.0:-2.0)*PI/(double)size;
	fs mul(cos(ang),sin(ang));
	u[0]=fs(1,0);
	for(int i=1;i<size/2;i++)u[i]=u[i-1]*mul;
	for(int step=2;step<=size;step<<=1){
		int gap=step>>1,addgap=size/step;
		for(int i=0;i<size;i+=step){
			for(int j=i;j<i+gap;j++){
				int k1=(j-i)*addgap;
				int k2=k1+addgap*gap;
				fs new1=A[j]+A[j+gap]*u[k1];
				fs new2=A[j]-A[j+gap]*u[k1];
				A[j]=new1,A[j+gap]=new2;
			}
		}
	}
	if(!flag)for(int i=0;i<size;i++)A[i]/=(double)size;
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n>>m;n++,m++;
	int sz=1;
	while(sz<n+m-1)sz<<=1;
	for(int i=0;i<n;i++){
		int x;cin>>x;A[i]=fs(x);
	}
	for(int i=0;i<m;i++){
		int x;cin>>x;B[i]=fs(x);
	}
	FFT(A,sz,true);FFT(B,sz,true); 
	for(int i=0;i<sz;i++)A[i]=A[i]*B[i];
	FFT(A,sz,false);
	for(int i=0;i<n+m-1;i++)cout<<(int)(A[i].real+0.5)<<' ';
	return 0;
}