洛谷P3803 【模板】多项式乘法（FFT）

Code: 

#include<bits/stdc++.h>
#define maxn 5000001
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
const double pi=acos(-1.0);
struct cpx
{
double x,y;
cpx(double a=0,double b=0) {x=a, y=b; }
cpx operator+(const cpx b) { return cpx(x+b.x,y+b.y); }
cpx operator-(const cpx b) { return cpx(x-b.x,y-b.y); }
cpx operator*(const cpx b) { return cpx(x*b.x-y*b.y,x*b.y+y*b.x); }
}A[maxn],B[maxn];
void FFT(cpx *a,int n,int flag)
{
for(int i=0,k=0;i<n;++i)
{
if(i>k) swap(a[i], a[k]);
for(int j=n>>1;(k^=j)<j;j>>=1);
}
for(int mid=1;mid<n;mid<<=1)
{
cpx wn(cos(pi/mid), flag*sin(pi/mid)),x,y;
for(int j=0;j<n;j+=(mid<<1))
{
cpx w(1,0);
for(int k=0;k<mid;++k)
{
x=a[j+k], y=w*a[j+k+mid];
a[j+k]=x+y,a[j+k+mid]=x-y;
w=w*wn;
}
}
}
if(flag==-1)
for(int i=0;i<n;++i) a[i].x/=(double)n;
}
int main()
{
// setIO("input");
int n,m,len=1;
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);
for(len=1;len<(n+m+1);len<<=1);
FFT(A, len, 1), FFT(B, len, 1);
for(int i=0;i<len;++i) A[i]=A[i]*B[i];
FFT(A, len, -1);
for(int i=0;i<=n+m;++i) printf("%d ",(int)(A[i].x+0.5));
return 0;
}