我写的什么FFT啊
查看原帖
我写的什么FFT啊
549499
Disjoint_cat楼主2022/11/12 21:40

样例都过不了

#include<bits/stdc++.h>
#define ll long long
#define db double
using namespace std;
const int MAXN=1<<22;
const db PI=acos(1.0);
struct cmplx//手写复数类
{
	db re,im;//re实部,im虚部
	cmplx(db RE=0.0,db IM=0.0):re(RE),im(IM){}
};
int N,M,rawT,T,Max,TYPE;
cmplx a[MAXN],b[MAXN];
cmplx operator+(cmplx A,cmplx B){return cmplx(A.re+B.re,A.im+B.im);}
cmplx operator-(cmplx A,cmplx B){return cmplx(A.re-B.re,A.im-B.im);}
cmplx operator*(cmplx A,cmplx B){return cmplx(A.re*B.re-A.im*B.im,\
A.re*B.im+A.im*B.re);}
cmplx E(int n){return cmplx(cos(2*PI/n),TYPE*sin(2*PI/n));}
void transform(cmplx *a,const int n)//fast fast TLE
{
	if(n==1)return;
	cmplx a0[n>>1],a1[n>>1];
	for(int i=0;i<n;i++)
		if(i&1)a1[i>>1]=a[i];else a0[i>>1]=a[i];
	transform(a0,n>>1);
	transform(a1,n>>1);
	cmplx t=E(n);
	for(int i=0;i<n;i++)
	{
		if(i&1)a[i]=a1[i-1>>1]*t;
		else a[i]=a0[i>>1];
	}
}
int main()
{
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>N>>M;T=1;
	for(int i=0;i<=N;i++)cin>>a[i].re;
	for(int i=0;i<=M;i++)cin>>b[i].re;
	while(T<N+M)T<<=1;
	TYPE=1;
	transform(a,T);
	transform(b,T);
	for(int i=0;i<T;i++)a[i]=a[i]*b[i];
	TYPE=-1;
	transform(a,T);
	for(int i=0;i<=N+M;i++)cout<<a[i].re/T<<" ";
	return 0;
}
2022/11/12 21:40
加载中...