LG3803 「模板」快速傅里叶变换 FFT

问题描述

LG3803

---

题解

点我

---

(mathrm{Code})

#include<bits/stdc++.h>
using namespace std;

const int maxn=1350000;
const double Pi=acos(-1);
int n,m;

struct CP{
	CP(double X=0,double Y=0) {x=X,y=Y;}
	double x,y;
	CP operator + (CP const &a) const
	{return CP(x+a.x,y+a.y);}
	CP operator - (CP const &a) const
	{return CP(x-a.x,y-a.y);}
	CP operator * (CP const &a) const
	{return CP(x*a.x-y*a.y,x*a.y+y*a.x);}
}f[maxn<<1],p[maxn<<1];

int tr[maxn<<1];

void fft(CP *f,bool type){
	for(int i=0;i<n;i++) if(i<tr[i]) swap(f[i],f[tr[i]]);
	for(int p=2;p<=n;p<<=1){
		int len=p>>1;
		CP tG(cos(2*Pi/p),sin(2*Pi/p));
		if(!type) tG.y*=-1;
		for(int k=0;k<n;k+=p){
			CP buf(1,0);
			for(int l=k;l<k+len;l++){
				CP tt=buf*f[l+len];
				f[l+len]=f[l]-tt;
				f[l]=f[l]+tt;
				buf=buf*tG;
			}
		}
	}
}

int main(){
	scanf("%d%d",&n,&m);
	for(int i=0;i<=n;i++) scanf("%lf",&f[i].x);
	for(int i=0;i<=m;i++) scanf("%lf",&p[i].x);
	for(m+=n,n=1;n<=m;n<<=1);
	for(int i=0;i<n;i++) tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
	fft(f,1);fft(p,1);
	for(int i=0;i<n;i++) f[i]=f[i]*p[i];
	fft(f,0);
	for(int i=0;i<=m;i++){
		printf("%d ",(int)(f[i].x/n+0.49));
	}
}