代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <vector>
#include <stack>
#include <map>
#include <bitset>
#define ri register
#define inf 0x7fffffff
#define E (1)
#define mk make_pair
//#define int long long
//#define double long double
using namespace std; const int MAXN=4000010; const double pi=acos(-1.0);
inline int read()
{
    int s=0, w=1; ri char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') w=-1; ch=getchar(); }
    while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch-'0'), ch=getchar();
    return s*w;
}
void print(int x) { if(x<0) x=-x, putchar('-'); if(x>9) print(x/10); putchar(x%10+'0'); }
int n,m,N=1,bit,rev[MAXN];
inline void Get_Rev() { for(ri int i=0;i<N;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1)); }
struct Complex
{
    double x,y;
    inline Complex (double pp=0, double qq=0) { x=pp, y=qq; }
}a[MAXN],b[MAXN];
inline Complex operator + (Complex a,Complex b) { return Complex(a.x+b.x,a.y+b.y); }
inline Complex operator - (Complex a,Complex b) { return Complex(a.x-b.x,a.y-b.y); }
inline Complex operator * (Complex a,Complex b) { return Complex(a.x*b.x-a.y*b.y,a.x*b.y+b.x*a.y); }
inline void FFT(Complex *s,int type)
{
    for(ri int i=0;i<N;i++) if(i<rev[i]) swap(s[i],s[rev[i]]);
    for(ri int mid=1;mid<N;mid<<=1)
    {
        Complex wn(cos(pi/mid),type*sin(pi/mid));
        for(ri int r=mid<<1, j=0;j<N;j+=r)
        {
            Complex w(1,0);
            for(ri int k=0;k<mid;k++, w=w*wn)
            {
                Complex x=s[j+k], y=w*s[j+mid+k];
                s[j+k]=x+y, s[j+mid+k]=x-y;
            }
        }
    }
}
signed main()
{
    n=read(), m=read();
    for(ri int i=0;i<=n;i++) a[i].x=read();
    for(ri int i=0;i<=m;i++) b[i].x=read();
    while(N<=(n+m)) N<<=1, bit++;
    Get_Rev();
    FFT(a,1), FFT(b,1);
    for(ri int i=0;i<N;i++) a[i]=a[i]*b[i];
    FFT(a,-1);
    for(ri int i=0;i<=n+m;i++) printf("%d ",(int)(a[i].x/N+0.5));
    puts("");
    return 0;
}

评测结果