代码

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

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

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

  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;
  }
} cin;

struct Complex {
  double x, y;

  Complex() {}

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

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

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

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

constexpr double pi = acos(-1.);

int to[1<<21|1];

void FFT(int N, Complex *a, int type) {
  for (int i = 0; i < N; ++i)
    if (i < to[i]) std::swap(a[i], a[to[i]]);

  Complex rt, w, t1, t2;
  for (int m = 1; m < N; m <<= 1) {
    rt = Complex(cos(pi / m), type * sin(pi / m));
    for (int j = 0; j < N; 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 < N; ++i)
      a[i].x /= N, a[i].y /= N;
}

int main() {
  int N, M, lim, l;

  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(lim, F, 1);
  for (int i = 0; i < lim; ++i)
    F[i] = F[i] * F[i];
  FFT(lim, F, -1);
  for (int i = 0; i <= N + M; ++i)
    std::cout << int(F[i].y / 2 + 0.5) << ' ';
  return 0;
}

评测结果