关于评测疑惑
查看原帖
关于评测疑惑
714325
EXR_FAL楼主2025/1/16 20:24

对于下面的代码,在洛谷上评测为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;
}
2025/1/16 20:24
加载中...