代码

#include<algorithm>
#include<cmath>
#include<cstdio>

static char ibuf[1<<20|1], obuf[1<<20|1], *p1 = ibuf, *p2 = ibuf, *p3 = obuf;

struct IO {
  char gc() {
    return p1 == p2 && (p2 = (p1 = ibuf) + fread(ibuf, 1, 1 << 20 | 1, stdin)) ? EOF : *p1++;
  }

  void flush() {
    fwrite(obuf, 1, p3 - obuf, stdout), p3 = obuf;
  }

  template<typename T>
  IO operator>>(T &n) {
    n = 0; char c = gc();
    while (c < '0' || c > '9') c = gc();
    while (c >= '0' && c <= '9') n = n * 10 + (c ^ 48), c = gc();
    return *this;
  }

  IO operator<<(char n) {
    if (p3 - obuf == (1 << 20 | 1)) flush();
    *p3++ = n;
    return *this;
  }

  template<typename T>
  IO operator<<(T n) {
    static int stk[41];
    int top = 0;
    do stk[top++] = n % 10 + 48; while (n /= 10);
    while (top) *this << char(stk[--top]);
    return *this;
  }
} cin, cout;

constexpr double pi = acos(-1.);

int N, M, lim, l, to[1<<21|1];

struct Complex {
  double x, y;

  Complex() {}

  Complex(double X, double Y): x(X), y(Y) {}

  Complex operator+(const Complex &rhs) const {
    return Complex(x + rhs.x, y + rhs.y);
  }

  Complex operator-(const Complex &rhs) const {
    return Complex(x - rhs.x, y - rhs.y);
  }

  Complex operator*(const Complex &rhs) const {
    return Complex(x * rhs.x - y * rhs.y, x * rhs.y + y * rhs.x);
  }
} F[1<<21|1];

void FFT(Complex *a, int type) {
  for (int i = 0; i <= lim; ++i)
    if (i < to[i]) std::swap(a[i], a[to[i]]);
  Complex rt, w, t1, t2;
  for (int m = 1; m < lim; m <<= 1) {
    rt = Complex(cos(pi / m), type * sin(pi / m));
    for (int j = 0; j < lim; j += m << 1) {
      w = Complex(1, 0);
      for (int k = 0; k < m; ++k, w = w * rt) {
        t1 = a[j | k], t2 = w * a[j | k | m];
        a[j | k] = t1 + t2, a[j | k | m] = t1 - t2;
      }
    }
  }
  if (type == -1)
    for (int i = 0; i <= lim; ++i)
      a[i].x /= lim, a[i].y /= lim;
}

int main() {
  cin >> N >> M;
  for (lim = 1, l = -1; lim <= N + M; lim <<= 1, ++l);
  for (int i = 0; i <= lim; ++i)
    to[i] = (to[i >> 1] >> 1) | ((i & 1) << l);
  for (int i = 0, t; i <= N; ++i)
    cin >> t, F[i].x = t;
  for (int i = 0, t; i <= M; ++i)
    cin >> t, F[i].y = t;
  FFT(F, 1);
  for (int i = 0; i <= lim; ++i)
    F[i] = F[i] * F[i];
  FFT(F, -1);
  for (int i = 0; i <= N + M; ++i)
    cout << int(F[i].y / 2 + 0.5) << ' ';
  cout.flush();
  return 0;
}

评测结果