0分求助
查看原帖
0分求助
534323
vector11楼主2023/7/7 21:02

前七个点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;
} 
2023/7/7 21:02
加载中...