FFT递归求助
查看原帖
FFT递归求助
328935
calmsGZ省队2024楼主2023/3/11 18:02
#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;

const int maxn=4*1e6+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 limit,complex *a,int type){
	if(limit==1)return;
	complex a1[limit>>1],a2[limit>>1];
	for(int i=0;i<=limit;i+=2){
		a1[i>>1]=a[i];
		a2[i>>1]=a[i+1];
	}
	fft(limit>>1,a1,type);
	fft(limit>>1,a2,type);
	complex wn=complex(cos(2.0*pi/limit),type*sin(2.0*pi/limit));
	complex w=complex(1,0);
	for(int i=0;i<(limit>>1);i++,w=w*wn){
		a[i]=a1[i]+w*a2[i];
		a[i+(limit>>1)]=a1[i]-w*a2[i];
	}
}

int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=0;i<=n;i++)scanf("%lf",&a[i].x);
	for(int i=0;i<=m;i++)scanf("%lf",&b[i].x);
	int limit=1;
	while(limit<=n+m)limit<<=1;
	fft(limit,a,1);
	fft(limit,b,1);
	for(int i=0;i<=limit;i++){
	
	//	cout<<a[i]<<" "<<b[i]<<endl;
		a[i]=a[i]*b[i];

	}
	fft(limit,a,-1);
	for(int i=0;i<=n+m;i++)printf("%d ",(int)(a[i].x/limit+0.5));
}
2023/3/11 18:02
加载中...