FFT模闆（UOJ34多項式乘法）

#include <bits/stdc++.h>
#define ll long long
#define gc getchar()
#define N 400009
#define Pi acos(-1.0)
using namespace std;
int n,m,l,ans[N];
struct Complex
{
	double p,q;
	Complex(double p=0,double q=0):p(p),q(q){}
	Complex operator +(const Complex add)
	{
		return Complex(p+add.p,q+add.q);
	}
	Complex operator -(const Complex add)
	{
		return Complex(p-add.p,q-add.q);
	}
	Complex operator *(const Complex add)
	{
		return Complex(p*add.p-q*add.q,p*add.q+q*add.p);
	}
}x1[N],x2[N];
int read()
{
	int x=1;
	char ch;
	while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1;
	int s=ch-'0';
	while (ch=gc,ch>='0'&&ch<='9') s=s*10+ch-'0';
	return s*x;
}
void brc(Complex *y,int l)
{
	for (int i=1,j=l/2;i<l-1;i++)
	{
		if (i<j) swap(y[i],y[j]);
		int k=l/2;
		while (j>=k)
		{
			j-=k;
			k/=2;
		}
		if (j<k) j+=k;
	}
}
void FFT(Complex *y,int l,int on)
{
	Complex u,t;
	brc(y,l);
	for (int h=2;h<=l;h<<=1)
	{
		Complex wn=Complex(cos(on*2*Pi/h),sin(on*2*Pi/h));
		for (int i=0;i<l;i+=h)
		{
			Complex w=Complex(1,0);
			for (int j=i;j<i+h/2;j++)
			{
				u=y[j];
				t=w*y[j+h/2];
				y[j]=u+t;
				y[j+h/2]=u-t;
				w=w*wn;
			}
		}
	}
	if (on==-1)
		for (int i=0;i<l;i++) y[i].p/=l;
}
int main()
{
	n=read(),m=read(),l=1;
	while (l<((n+1)<<1)|l<((m+1)<<1)) l<<=1;
	for (int i=0;i<l;i++)
		x1[i]=Complex((i<=n)?(double)read():0.0,0.0);
	for (int j=0;j<l;j++)
		x2[j]=Complex((j<=m)?(double)read():0.0,0.0);
	FFT(x1,l,1);
	FFT(x2,l,1);
	for (int i=0;i<l;i++) x1[i]=x1[i]*x2[i];
	FFT(x1,l,-1);
	for (int i=0;i<=n+m;i++)
		printf("%d\n",ans[i]=x1[i].p+0.5);
	return 0;
}