前七个点WA,最后两个点RE
样例过了,第一个数据在本地也过了
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m;
const int maxn=2e6+10;
const double PI=acos(-1.0);
struct complex{
double x,y;
complex (double xx=0,double yy=0){x=xx,y=yy;}
}a[maxn],b[maxn];
complex operator + (complex a,complex b){
return complex(a.x+b.x,a.y+b.y);
}
complex operator - (complex a,complex b){
return complex(a.x-b.x,a.y-b.y);
}
complex operator * (complex a,complex b){
return complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);
}
void fft(int lim,complex *a,int type){
if(lim==1) return;
complex a1[lim>>1],a2[lim>>1];
for(int i=0;i<=lim;i+=2){
a1[i>>1]=a[i];
a2[i>>1]=a[i+1];
}
fft(lim>>1,a1,type);
fft(lim>>1,a2,type);
complex Omega=complex(cos(2.0*PI/lim),type*sin(2.0*PI/lim));
complex Power=complex(1,0);
for(int i=0;i<(lim>>1);i++,Power=Power*Omega)
{
complex t=Power*a2[i];
a[i]=a1[i]+t;
a[i+(lim>>1)]=a1[i]-t;
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++){
scanf("%lf",&a[i].x);
// cout << a[i-]
}
for(int i=0;i<=m;i++){
scanf("%lf",&b[i].x);
}
int Lim=1;
while(Lim<=n+m) Lim<<=1;
fft(Lim,a,1);
fft(Lim,b,1);
for(int i=0;i<=Lim;i++){
a[i]=a[i]*b[i];
}
fft(Lim,a,-1);
for(int i=0;i<=n+m-1;i++){
printf("%d ",(int)(a[i].x/Lim+0.5));
}
cout<<(int)(a[m+n].x/Lim+0.5);
return 0;
}