萌新刚学OI,WA #2,3 递推FFT求助
查看原帖
萌新刚学OI,WA #2,3 递推FFT求助
225883
MiRaciss楼主2023/1/26 09:04
#include<bits/stdc++.h>
using namespace std;
#define db double
const db PI=acos(-1.0);

int n,m;
struct zz{
	db x,y;
}a[4000005],b[4000005];
zz operator + (zz x,zz y){ return (zz){x.x+y.x,x.y+y.y}; }
zz operator - (zz x,zz y){ return (zz){x.x-y.x,x.y-y.y}; }
zz operator * (zz x,zz y){ return (zz){x.x*y.x-x.y*y.y,x.x*y.y+x.y*y.x}; }
int r[4000005];

void FFT(zz *a,int n,int op){
	if(!n) return ;
	for(int i=0;i<n;i++) if(i<r[i]) swap(a[i],a[r[i]]);
	for(int len=1;len<n;len<<=1){
		zz W=(zz){cos(PI/len),sin(PI/len)*op};
		for(int i=0;i<n;i+=(len<<1)){
			zz w=(zz){1,0};
			for(int j=0;j<len;j++,w=w*W){
				zz x=a[i+j],y=w*a[i+j+len];
				a[i+j]=x+y,a[i+j+len]=x-y;
			}
		}
	}
	if(op==1) return ;
	for(int i=0;i<n;i++) a[i].x/=n;
}

int main(){
	cin>>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 Max=1,l=0;while(Max<(n+m)) Max<<=1,l++;
	for(int i=0;i<Max;i++) r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
	FFT(a,Max,1),FFT(b,Max,1);
	for(int i=0;i<Max;i++) a[i]=a[i]*b[i];
	FFT(a,Max,-1);
	for(int i=0;i<=n+m;i++) printf("%.0f ",fabs(a[i].x));
	return 0;
}
2023/1/26 09:04
加载中...