代码

#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int Maxn=300005;
const double pi=acos(-1);
inline char C(){
    static char buf[1<<20],*S=buf,*T=S;
    return S==T&&(T=(S=buf)+fread(buf,1,1<<20,stdin),S==T)?EOF:*S++;
}
inline int read(){
    char c;int rec=0;
    while((c=C())<'0'||c>'9');
    while(c>='0'&&c<='9')rec=rec*10+c-'0',c=C();
    return rec;
}
char B[1<<20],*S=B;
inline void Out(int x){
	char stack[20],top=0;
	stack[++top]=' ';if(!x)stack[++top]='0';
	while(x)stack[++top]=x%10+'0',x/=10;
	while(top)*S++=stack[top--];return ;
}
int n,m,D,R[Maxn];
char ssr[Maxn];
int ans[Maxn];
struct Cp{
    double r,i;
    inline Cp operator+(Cp x){return (Cp){r+x.r,i+x.i};}
    inline Cp operator-(Cp x){return (Cp){r-x.r,i-x.i};}
    inline Cp operator*(Cp x){return (Cp){r*x.r-i*x.i,r*x.i+i*x.r};}    
}a[Maxn],b[Maxn],temp[Maxn];
inline void Fft(Cp *x,int f){
    for(int i=0;i<n;++i)temp[i]=x[R[i]];
    for(int i=0;i<n;++i)x[i]=temp[i];
    temp[0]=(Cp){1,0};
    for(int s=2;s<=n;s<<=1){
        Cp wn=(Cp){cos(2*pi/s),f*sin(2*pi/s)};
        for(int j=1;j<(s>>1);++j)temp[j]=temp[j-1]*wn;
        for(int k=0;k<n;k+=s){
            Cp t,u;
            for(int j=0;j<(s>>1);++j){
                t=temp[j]*x[k+j+(s>>1)];
                u=x[k+j];
                x[k+j]=u+t;x[k+j+(s>>1)]=u-t;
            }
        }
    }
    if(f==-1)for(int i=0;i<=n;++i)x[i].r/=n;
    return ;
}
int main(){
    n=read();m=read();
    for(int i=0,x;i<=n;++i)x=read(),a[i].r=x;
    for(int i=0,x;i<=m;++i)x=read(),b[i].r=x;
    m+=n;for(n=1;n<=m;n<<=1,++D);
    for(int i=0;i<n;++i)R[i]=(R[i>>1]>>1)|((i&1)<<(D-1));
    Fft(a,1);Fft(b,1);
    for(int i=0;i<=n;++i)a[i]=a[i]*b[i];
    Fft(a,-1);
    for(int i=0;i<=m;++i)Out((int)(a[i].r+0.5));
    fwrite(B,1,S-B,stdout);
    return 0;
}

评测结果