# 2. 题解

//这个递归方法过不了 LUOGU 的 $10^6$的数据，但能过 LOJ 的 $10^5$的数据。这个方法下面有蝶型算法的代码哦 QvQ

xzy 太弱了

QAQ.jpg

#include <bits/stdc++.h>
#define NS (400000)
using namespace std;
typedef complex<double> cpx;
int n,m;
cpx a[NS],b[NS],buff[NS];
void FFT(cpx*c,int n,int t)
{
if(n==1)return;
int mid=(n>>1);
for(int i=0;i<mid;i++)buff[i]=c[i<<1],buff[i+mid]=c[i<<1|1];
copy(buff,buff+n,c);
cpx*c0=c,*c1=c+mid;
FFT(c0,mid,t),FFT(c1,mid,t);
cpx w(1,0),wn(cos(M_PI*2ll/n),t*sin(M_PI*2ll/n));
for(int i=0;i<mid;i++,w*=wn)
buff[i]=c0[i]+w*c1[i],buff[i+mid]=c0[i]-w*c1[i];
copy(buff,buff+n,c);
}
int main()
{
scanf("%d%d",&n,&m);
double tmp;
for(int i=0;i<=n;i++)scanf("%lf",&tmp),a[i].real(tmp);
for(int i=0;i<=m;i++)scanf("%lf",&tmp),b[i].real(tmp);
int len=1;while(len<=n+m)len<<=1;
FFT(a,len,1),FFT(b,len,1);
for(int i=0;i<=len;i++)a[i]*=b[i];
FFT(a,len,-1);
for(int i=0;i<=n+m;i++)printf("%d ",(int)(a[i].real()/len+0.5));
return 0;
}


# Update

#include <bits/stdc++.h>
#define NS (3000005)
using namespace std;
typedef complex<double> cpx;
int n,m,rev[NS];
cpx Fa[NS],Fb[NS];
void FFT(cpx*a,int lg,int t)
{
int len=(1<<lg);
for(int i=0;i<len;i++)if(i<rev[i])swap(a[i],a[rev[i]]);
for(int l=1;l<len;l<<=1)
for(int s=0;s<len;s+=(l<<1))
{
cpx w(1,0),wn(cos(M_PI/l),t*sin(M_PI/l)),t0,t1;
for(int i=s;i<s+l;i++,w*=wn)
t0=a[i],t1=w*a[i+l],a[i]=t0+t1,a[i+l]=t0-t1;
}
}
int main()
{
scanf("%d%d",&n,&m);
double tmp;
for(int i=0;i<=n;i++)scanf("%lf",&tmp),Fa[i].real(tmp);
for(int i=0;i<=m;i++)scanf("%lf",&tmp),Fb[i].real(tmp);
int lg=0;while((1<<lg)<=n+m)lg++;
for(int i=0;i<(1<<lg);i++)rev[i]=(rev[i>>1]>>1)|((i&1)<<(lg-1));
FFT(Fa,lg,1),FFT(Fb,lg,1);
for(int i=0;i<(1<<lg);i++)Fa[i]*=Fb[i];
FFT(Fa,lg,-1);
for(int i=0;i<=n+m;i++)printf("%d ",(int)(Fa[i].real()/(1<<lg)+0.5));
return 0;
}