对于下面的代码,在洛谷上评测为0分
但是此代码不仅在本地通过了样例,通过下载数据也顺利通过下载下来的数据,但不知道为什么就是0分
洛谷数据#1:
in:
5 5
1 7 4 0 9 4
8 8 2 4 5 5
out:
8 64 90 50 113 160 105 64 61 65 20
我本地的out:
8 64 90 50 113 160 105 64 61 65 20
理论上来说没有问题啊啊啊啊啊啊,求解答
代码:
#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
inline ll read(){
ll x=0,flag=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')flag=-1;ch=getchar();}
while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
return x*flag;
}
void out(ll x){
if(x<0)putchar('-'),x=-x;
if(x<10)putchar(x+'0');
else out(x/10),putchar(x%10+'0');
}
const double PI=acos(-1);
const int N=2.2e6+114;
int n,m;
//Complex Number
struct Complex{
double x,y;
Complex(double x=0,double y=0){
this->x=x;
this->y=y;
}
friend Complex operator +(Complex a,Complex b){
return (Complex){a.x+b.x,a.y+b.y};
}
friend Complex operator -(Complex a,Complex b){
return (Complex){a.x-b.x,a.y-b.y};
}
friend Complex operator *(Complex a,Complex b){
return (Complex){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};
}
}a[N],b[N];
////Fast Fourier
void FFT(int lim,Complex *a,int typ){
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,typ);
FFT(lim>>1,a2,typ);
Complex Wn=(Complex){cos(2.0*PI/lim),typ*sin(2.0*PI/lim)};
Complex W=(Complex){1,0};
for(int i=0;i<(lim>>1);i++,W=W*Wn){
a[i]=a1[i]+W*a2[i];
a[i+(lim>>1)]=a1[i]-W*a2[i];
}
}
signed main(){
n=read(),m=read();
for(int i=0;i<=n;i++) a[i].x=read();
for(int i=0;i<=m;i++) b[i].x=read();
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;i++)
printf("%d ",(int)(a[i].x/lim+0.5));
return 0;
}