求救,为什么WA了???
查看原帖
求救,为什么WA了???
110685
James0602楼主2021/2/12 08:19

FFT,最后两个点一直是WA的,能不能帮我看看??

#include<cmath>
#include<math.h>
#include<cstdio>
#include<complex>
#include<iostream>
#include<algorithm>
#define PI M_PI
#define N 1000005
using namespace std;
int n,m1,m2;
int rev[N];
complex<double>A[N],B[N];
void FFT(complex<double> *A, int type) {
	for (int i=0;i<n;++i)
		if (i<rev[i]) swap(A[i],A[rev[i]]);
	for (int j=1;j<n;j<<=1){
		complex<double>W(cos(PI/j),sin(PI/j)*type);
		for (int k=0;k<n;k+=(j<<1)){
			complex<double>w(1.0,0.0);
			for (int i=0;i<j;++i){
				complex<double>ye,yo;
				ye=A[i+k];yo=A[i+j+k]*w;
				A[i+k]=ye+yo;
				A[i+j+k]=ye-yo;
				w*=W;
			}
		}
	}
	return;
}
int main(){
	scanf("%d%d",&m1,&m2);
	for (int i=0;i<=m1;++i) cin>>A[i];
	for (int i=0;i<=m2;++i) cin>>B[i];
	n=m1+m2;
	for (int i=1;i<=20;++i) if ((1<<i)>n){
		n=1<<i;
		break;
	}
	for (int i=0;i<n;++i)
		rev[i]=(rev[i>>1]>>1)|((i&1)?(n>>1):0);
	FFT(A,1);FFT(B,1);
	for (int i=0;i<=n;++i)
		A[i]*=B[i];
	FFT(A,-1);
	for (int i=0;i<=m1+m2;++i)
		printf("%d ",(int)(A[i].real()/(double)n+0.5));
	return 0;
}
2021/2/12 08:19
加载中...