代码

#include <bits/stdc++.h>

#define file(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)

#define Enter putchar('\n')
#define quad putchar(' ')

#define N 3000005

namespace IO {

template <class T>
inline void read(T &a);
template <class T, class ...rest>
inline void read(T &a, rest &...x);

template <class T>
inline void write(T x);

}

struct cp {
  double x, y;
  cp (double xx = 0, double yy = 0) {x = xx; y = yy;};

  friend cp operator +(cp p, cp q) {return cp(p.x + q.x, p.y + q.y);}
  friend cp operator -(cp p, cp q) {return cp(p.x - q.x, p.y - q.y);}
  friend cp operator *(cp p, cp q) {return cp(p.x * q.x - p.y * q.y, p.y * q.x + p.x * q.y);}
}a[N], b[N];

const double pi = 3.1415926535;

int n1, n2, n, rev[N], c[N];

inline void FFT(cp *a, int n, int inv) {
  int bit = 0;
  while ((1 << bit) < n) bit++;
  for (int i = 1; i < n; ++i) {
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (bit - 1));
    if (i < rev[i])
      std::swap(a[rev[i]], a[i]);
  }
  for (int mid = 1; mid < n; mid <<= 1) {
    cp temp(cos(pi / mid), inv * sin(pi / mid));
    for (int i = 0; i < n; i += mid * 2) {
      cp omega(1,0);
      for (int j = 0; j < mid; ++j, omega = omega * temp) {
        cp x = a[i + j], y = omega * a[i + j + mid];
        a[i + j] = x + y;
        a[i + j + mid] = x - y;
      }
    }
  }
}

signed main(void) {
  // file("P3803");
  IO::read(n1, n2);
  n = std::max(n1, n2);
  for (int i = 0, num; i <= n1; ++i) IO::read(num), a[i].x = num;
  for (int i = 0, num; i <= n2; ++i) IO::read(num), b[i].x = num;
  n = n1 + n2;
  for (int i = 0; i <= 30; ++i)
    if ((1 << i) > n) {
      n = (1 << i);
      break;
    }

  FFT(a, n, 1); FFT(b, n, 1);
  for (int i = 0; i < n; ++i) a[i] = a[i] * b[i];
  FFT(a, n, -1);
  for (int i = 0; i <= n1 + n2; ++i)
    c[i] = (int)(a[i].x / n + 0.5);
  
  for (int i = 0; i <= n1 + n2; ++i)
    IO::write(c[i]), quad;
  Enter;
}

namespace IO {

template <class T>
inline void read(T &a) {
  T s = 0, t = 1;
  char c = getchar();
  while ((c < '0' || c > '9') && c != '-')
    c = getchar();
  if (c == '-')
    c = getchar(), t = -1;
  while (c >= '0' && c <= '9')
    s = (s << 1) + (s << 3) + (c ^ 48), c = getchar();
  a = s * t;
}
template <class T, class ...rest>
inline void read(T &a, rest &...x) {
  read(a);
  read(x...);
}

template <class T>
inline void write(T x) {
  if (x == 0) putchar('0');
  if (x < 0) putchar('-'), x = -x;
  int top = 0, sta[55] = {0};
  while (x) 
    sta[++top] = x % 10, x /= 10;
  while (top)
    putchar(sta[top] + '0'), top--;
  return ;
}

}

评测结果