代码

#ifndef LOCAL
#define NDEBUG
#endif
#include <algorithm>
#include <cassert>
#include <cstring>
#include <functional>
#include <initializer_list>
#include <iostream>
#include <memory>
#include <queue>
#include <random>
#include <vector>

struct Complex {
public:
  double real, imag;
  using cpx = Complex;
  Complex() = default;
  Complex(const cpx &rhs) : real(rhs.real), imag(rhs.imag) {}
  ~Complex() = default;
  Complex(const double &r) : real(r), imag(0) {}
  Complex(const double &r, const double &i) : real(r), imag(i) {}
  cpx &operator=(const cpx &rhs) { return real = rhs.real, imag = rhs.imag, *this; }
  cpx operator-() const { return cpx(-real, -imag); }
  cpx &operator+=(const cpx &rhs) { return real += rhs.real, imag += rhs.imag, *this; }
  cpx &operator-=(const cpx &rhs) { return real -= rhs.real, imag -= rhs.imag, *this; }
  cpx &operator*=(const cpx &rhs) { // 没有必要使用三次乘法与更多次加法
    double r = real * rhs.real - imag * rhs.imag, i = real * rhs.imag + imag * rhs.real;
    return real = r, imag = i, *this;
  }
  cpx &operator/=(const cpx &rhs) {
    double t = rhs.real * rhs.real + rhs.imag * rhs.imag, r = real * rhs.real + imag * rhs.imag,
           i = imag * rhs.real - real * rhs.imag;
    return real = r / t, imag = i / t, *this;
  }
  friend cpx operator+(const cpx &lhs, const cpx &rhs) { return cpx(lhs) += rhs; }
  friend cpx operator-(const cpx &lhs, const cpx &rhs) { return cpx(lhs) -= rhs; }
  friend cpx operator*(const cpx &lhs, const cpx &rhs) { return cpx(lhs) *= rhs; }
  friend cpx operator/(const cpx &lhs, const cpx &rhs) { return cpx(lhs) /= rhs; }
  friend cpx conj(const cpx &lhs) { return cpx(lhs.real, -lhs.imag); }
};

const Complex *init(int n) {
  static int lim = 0;
  static const double PI = std::acos(-1.0);
  static Complex ROOT[1 << 20];
  if (lim == 0) {
    ROOT[1 << 19] = Complex(std::cos(PI / (1 << 20)), std::sin(PI / (1 << 20)));
    for (int i = 18; i != -1; --i) ROOT[1 << i] = ROOT[1 << i + 1] * ROOT[1 << i + 1];
    lim = 1;
  }
  while ((lim << 1) < n) {
    for (int i = lim + 1, e = lim << 1; i < e; ++i) ROOT[i] = ROOT[i - lim] * ROOT[lim];
    lim <<= 1;
  }
  return ROOT;
}

void idft(int n, Complex x[], const Complex *ROOT) { // DIT
  for (int i = 2; i < n; i <<= 1) {
    for (int j = 0, l = i >> 1; j != l; ++j) {
      Complex u = x[j], v = x[j + l];
      x[j] = u + v, x[j + l] = u - v;
    }
    for (int j = i, l = i >> 1, m = 1; j != n; j += i, ++m) {
      Complex root = conj(ROOT[m]);
      for (int k = 0; k != l; ++k) {
        Complex u = x[j + k], v = x[j + k + l];
        x[j + k] = u + v, x[j + k + l] = (u - v) * root;
      }
    }
  }
  Complex iv = Complex(1) / Complex(n);
  for (int j = 0, l = n >> 1; j != l; ++j) {
    Complex u = x[j] * iv, v = x[j + l] * iv;
    x[j] = u + v, x[j + l] = u - v;
  }
}

void dft(int n, Complex x[], const Complex *ROOT) { // DIF
  for (int j = 0, l = n >> 1; j != l; ++j) {
    Complex u = x[j], v = x[j + l];
    x[j] = u + v, x[j + l] = u - v;
  }
  for (int i = n >> 1; i >= 2; i >>= 1) {
    for (int j = 0, l = i >> 1; j != l; ++j) {
      Complex u = x[j], v = x[j + l];
      x[j] = u + v, x[j + l] = u - v;
    }
    for (int j = i, l = i >> 1, m = 1; j != n; j += i, ++m) {
      Complex root = ROOT[m];
      for (int k = 0; k != l; ++k) {
        Complex u = x[j + k], v = x[j + k + l] * root;
        x[j + k] = u + v, x[j + k + l] = u - v;
      }
    }
  }
}

void dft(int n, Complex x[]) { dft(n, x, init(n)); }
void idft(int n, Complex x[]) { idft(n, x, init(n)); }

int main() {
#ifdef LOCAL
  std::freopen("..\\in", "r", stdin), std::freopen("..\\out", "w", stdout);
#endif
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  static Complex a[1 << 21], b[1 << 21];
  int n, m;
  std::cin >> n >> m;
  ++n, ++m;
  for (int i = 0; i != n; ++i) std::cin >> a[i].real;
  for (int i = 0; i != m; ++i) std::cin >> b[i].real;
  int l = n + m - 1, len = 1;
  while (len < l) len <<= 1;
  dft(len, a), dft(len, b);
  for (int i = 0; i != len; ++i) a[i] *= b[i];
  idft(len, a);
  for (int i = 0; i != l; ++i) std::cout << int(a[i].real + .5) << ' ';
  return 0;
}

评测结果