代码

#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 &) = default;
  ~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)); }

// https://uoj.ac/submission/390406 author: negiizhao

typedef unsigned int uint;
typedef long long unsigned int uint64;

struct IO_Tp
{
  const static int _I_Buffer_Size = 1 << 26;
  char _I_Buffer[_I_Buffer_Size], *_I_pos = _I_Buffer;
  
  const static int _O_Buffer_Size = 1 << 26;
  char _O_Buffer[_O_Buffer_Size], *_O_pos = _O_Buffer;
  
  uint m[10000];
  
  IO_Tp()
  {
    constexpr uint e0 = '\0\0\0\1', e1 = '\0\0\1\0', e2 = '\0\1\0\0', e3 = '\1\0\0\0';
    int x = 0;
    for (uint i = 0, c0 = '0000'; i != 10; ++i, c0 += e0)
      for (uint j = 0, c1 = c0; j != 10; ++j, c1 += e1)
        for (uint k = 0, c2 = c1; k != 10; ++k, c2 += e2)
          for (uint l = 0, c3 = c2; l != 10; ++l, c3 += e3)
            m[x++] = c3;
    
    fread(_I_Buffer, 1, _I_Buffer_Size, stdin);
  }
  ~IO_Tp() { fwrite(_O_Buffer, 1, _O_pos - _O_Buffer, stdout); }
  
  IO_Tp &operator>>(int &res)
  {
    while (!isdigit(*_I_pos))
      ++_I_pos;
    res = *_I_pos++ - '0';
    while (isdigit(*_I_pos))
      res = res * 10 + (*_I_pos++ - '0');
    return *this;
  }
  
  IO_Tp &operator>>(uint &res)
  {
    while (!isdigit(*_I_pos))
      ++_I_pos;
    res = *_I_pos++ - '0';
    while (isdigit(*_I_pos))
      res = res * 10 + (*_I_pos++ - '0');
    return *this;
  }
  
  IO_Tp &operator<<(uint x)
  {
    if (x == 0)
    {
      *_O_pos++ = '0';
      return *this; 
    }
    static char _buf[12];
    char *_pos = _buf + 12;
    if (x >= 10000)
      *--reinterpret_cast<uint *&>(_pos) = m[x % 10000], x /= 10000;
    if (x >= 10000)
      *--reinterpret_cast<uint *&>(_pos) = m[x % 10000], x /= 10000;
    *--reinterpret_cast<uint *&>(_pos) = m[x];
    _pos += (x < 1000) + (x < 100) + (x < 10);
    _O_pos = std::copy(_pos, _buf + 12, _O_pos);
    return *this;
  }
  
  IO_Tp &operator<<(char ch)
  {
    *_O_pos++ = ch;
    return *this;
  }
} io;

int main() {
  static Complex a[1 << 21];
  int n, m;
  io >> n >> m;
  ++n, ++m;
  unsigned int v;
  for (int i = 0; i != n; ++i) io >> v, a[i].real = v;
  for (int i = 0; i != m; ++i) io >> v, a[i].imag = v;
  int l = n + m - 1, len = 1;
  while (len < l) len <<= 1;
  dft(len, a);
  for (int i = 0; i != len; ++i) a[i] *= a[i];
  idft(len, a);
  for (int i = 0; i != l; ++i) io << (unsigned int)(a[i].imag / 2 + .5) << ' ';
  return 0;
}

评测结果