代码

// luogu-judger-enable-o2
#include <bits/stdc++.h>
using namespace std;
typedef complex<double> complex_t;
const int MAXN = 2610000;

namespace fast_io {
    inline char read(){static const int IN_LEN=1000000;static char buf[IN_LEN],*s,*t;return s==t?(((t=(s=buf)+fread(buf,1,IN_LEN,stdin))==s)?-1:*s++) : *s++;}
    inline void read(int &x){static bool iosig;static char c;for (iosig=false,c=read();!isdigit(c);c=read()){if(c=='-')iosig=true;if(c==-1)return;}for(x=0;isdigit(c);c=read())x=((x+(x<<2))<<1)+(c^'0');if(iosig)x=-x;}
    inline void read(char *a){static char c = read();while(c!=-1&&(c==' '||c=='\n'||c=='\r'))c=read();while(c!=-1&&c!='\r'&&c!=' '&&c!='\n') *a++=c,c=read();*a=0;}
    const int OUT_LEN=1000000;char obuf[OUT_LEN],*ooh=obuf;
    inline void print(char c){if(ooh==obuf+OUT_LEN) fwrite(obuf,1,OUT_LEN,stdout),ooh=obuf;*ooh++ = c;}
    inline void print(int x){static int buf[30],cnt;if(x==0)print('0');else{if(x<0)print('-'),x=-x;for(cnt=0;x;x/=10)buf[++cnt]=x%10+48;while (cnt) print((char)buf[cnt--]);}}
    inline void print(char *a){while(*a) print(*a++);}
    inline void flush(){fwrite(obuf,1,ooh-obuf,stdout);}
}using namespace fast_io;

namespace FFT{
const double PI = acos(-1.0);
// op == 1 -> DFT, op == -1 -> IDFT
void fft(complex_t *P,int n,int op){
    static int r[MAXN];
    int len = 0;
    for(int i = 1;i<n;i<<=1) len++;
    for(int i = 0;i < n;i++)
        r[i] = (r[i>>1]>>1) | ((i&1) << (len-1)); 
    for(int i = 0;i < n;i++)
        if(i < r[i]) swap(P[i],P[r[i]]);
    for(int i = 1;i<n;i<<=1){
        complex_t x(cos(PI/i),op*sin(PI/i));
        for(int j = 0;j<n;j+=(i<<1)){
            complex_t y(1,0);
            for(int k = 0;k<i;k++,y*=x){
                complex_t p=P[j+k],q=y*P[i+j+k];
                P[j+k] = p+q,P[i+j+k]=p-q;
            }
        }
    }
}
}

int n,m;
complex_t a[MAXN],b[MAXN];

int main(){
    read(n),read(m);
    int t;
    for(int i = 0;i<=n;i++){
        read(t);a[i] = t;
    }
    for(int i = 0;i<=m;i++){
        read(t);b[i] = t;
    }
    for(m+=n,n=1;n<=m;n<<=1);
    FFT::fft(a,n,1),FFT::fft(b,n,1);
    for(int i = 0;i<=n;i++)
        a[i] *= b[i]; 
    FFT::fft(a,n,-1);
    for(int i = 0;i<=m;i++)
        print(int(a[i].real()/n + 0.5)),print(' ');
    flush();
    return 0;
}

评测结果