FFT 板子
背板子的岁月又开始了
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cmath>
#define r register
#define rep(i,x,y) for(r ll i=x;i<=y;++i)
#define per(i,x,y) for(r ll i=x;i>=y;--i)
using namespace std;
typedef long long ll;
const ll V=(1e7+10)/2;
const double pi=acos(-1.0);
ll in()
{
ll res=0,f=1;
char ch;
while((ch=getchar())<‘0‘||ch>‘9‘)
if(ch==‘-‘) f=-1;
res=res*10+ch-48;
while((ch=getchar())>=‘0‘&&ch<=‘9‘)
res=res*10+ch-48;
return res*f;
}
ll n,m,f[V];
ll now,k;
struct complex
{
double x,y;
complex (double xx=0,double yy=0) { x=xx,y=yy; }
}a[V],b[V];
complex operator + (complex a,complex b) { return complex(a.x+b.x,a.y+b.y); }
complex operator - (complex a,complex b) { return complex(a.x-b.x,a.y-b.y); }
complex operator * (complex a,complex b) { return complex(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x); }
void FFT(complex *a,ll v)
{
rep(i,0,now-1)
if(i<f[i]) swap(a[i],a[f[i]]);
for(r ll mid=1;mid<now;mid<<=1)
{
complex Wn(cos(pi/mid),v*sin(pi/mid));
ll R=mid<<1;
for(r ll j=0;j<now;j+=R)
{
complex val(1,0);
for(r ll k=0;k<mid;++k,val=val*Wn)
{
complex x=a[j+k],y=val*a[j+mid+k];
a[j+k]=x+y;
a[j+mid+k]=x-y;
}
}
}
}
int main()
{
scanf("%lld%lld",&n,&m);
rep(i,0,n) a[i].x=in();
rep(i,0,m) b[i].x=in();
now=1;//单位根中的k值，默认为2的自然数次幂
while(now<=n+m) now<<=1,++k;
rep(i,0,now-1)
f[i]=(f[i>>1]>>1)|((i&1)<<(k-1));
FFT(a,1);
FFT(b,1);
rep(i,0,now) a[i]=a[i]*b[i];
FFT(a,-1);
rep(i,0,m+n)
printf("%lld ",(ll)(a[i].x/now+0.49));
return 0;
}