代码

#include <bits/stdc++.h>

using namespace std;

// #define LOCK_GETCHAR
// #define USE_INT_128

#if __cplusplus < 201400
#warning "Please use c++14 or higher."
#define CONSTEXPR_FUNC
#define ENABLE_IF_INT
#else
#define CONSTEXPR_FUNC constexpr
#define ENABLE_IF_INT , enable_if_t<_is_integer<T>, int> = 0
template <class T> constexpr bool _is_integer = numeric_limits<T>::is_integer;
template <> constexpr bool _is_integer<bool> = false;
template <> constexpr bool _is_integer<char> = false;
#ifdef USE_INT_128
template <> constexpr bool _is_integer<__int128> = true;
template <> constexpr bool _is_integer<__uint128_t> = true;
#endif
template <class T ENABLE_IF_INT>
constexpr T INF = numeric_limits<T>::max() >> 1;
#endif

#if !defined(_WIN32) && !defined(LOCK_GETCHAR)
#define getchar getchar_unlocked
#endif

#define il inline
#define mkp make_pair
#define fi first
#define se second
#define For(i, j, k) for (decltype(j - k) i = (j); i <= (k); ++i)     // NOLINT
#define ForDown(i, j, k) for (decltype(j - k) i = (j); i >= (k); --i) // NOLINT
#define pb push_back
#define eb emplace_back
#ifndef ONLINE_JUDGE
#define FileIO(filename)                                                       \
  freopen(filename ".in", "r", stdin);                                         \
  freopen(filename ".out", "w", stdout)
#else
#define FileIO(filename) void(0)
#endif

using ll = long long;
using uint = unsigned int;
using ull = unsigned long long;
using db = double;
using ldb = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
#ifdef USE_INT_128
using lll = __int128_t;
using ulll = __uint128_t;
#endif

// clang-format off
template<typename T> constexpr il T sq(const T & x){ return x * x; }
template<typename T> CONSTEXPR_FUNC il void cmin(T & x, const T &y){ x = min(x, y); }
template<typename T> CONSTEXPR_FUNC il void cmax(T & x, const T &y){ x = max(x, y);}
template<typename T> CONSTEXPR_FUNC il T qpow(T x, ull y, T mod){T ans = 1; x %= mod; while (y) { if(y & 1)(ans *= x) %= mod;(x *= x) %= mod; y >>= 1;} return ans;}
template<typename T> CONSTEXPR_FUNC il T qpow(T x, ull y){T ans = 1; while (y) {if(y & 1) ans *= x;x *= x;y >>= 1;} return ans;}
template<typename T ENABLE_IF_INT> il void read(T &x){ x = 0; int f = 1; int c = getchar(); while(!isdigit(c)) {if (c == '-') f = -1;c = getchar();} while(isdigit(c)) {x = x * 10 + c - '0';c = getchar();} x *= f;}
template<typename T, typename ... Args> il void read(T &x, Args &... y){ read(x); read(y...); }
// clang-format on

// File head end

namespace {
// constexpr ll MAXN = ...;
using Z = complex<db>;
vector<Z> poly_mul_mod(int n, const vector<Z> &x, const vector<Z> &y, Z c) {
  // assert(x.size() == n && y.size() == n);
  if (n & 1) {
    vector<Z> tmp(2 * n), res(n);
    For(i, 0, n - 1) For(j, 0, n - 1) tmp[i + j] += x[i] * y[j];
    For(i, 0, n - 1) res[i] += tmp[i] + tmp[i + n] * c;
    return res;
  } else {
    Z c2 = sqrt(c);
    int n2 = n >> 1;
    vector<Z> pm(x.begin(), x.begin() + n2), pp(x.begin(), x.begin() + n2),
        qm(y.begin(), y.begin() + n2), qp(y.begin(), y.begin() + n2), res(n);
    For(i, n2, n - 1) pm[i - n2] += c2 * x[i], pp[i - n2] -= c2 * x[i];
    For(i, n2, n - 1) qm[i - n2] += c2 * y[i], qp[i - n2] -= c2 * y[i];
    pm = poly_mul_mod(n2, pm, qm, c2);
    pp = poly_mul_mod(n2, pp, qp, -c2);
    // assert(pm.size() == n2 && pp.size() == n2);
    For(i, 0, n2 - 1) res[i] = (pm[i] + pp[i]) / Z(2);
    For(i, n2, n - 1) res[i] = (pm[i - n2] - pp[i - n2]) / (c2 * Z(2));
    return res;
  }
}
constexpr int BRUTE_LIM = 10;
il vector<Z> poly_mul(vector<Z> x, vector<Z> y) {
  int n1 = x.size(), n2 = y.size(), res_sz = n1 + n2 - 1, n = 1;
  while (BRUTE_LIM * n < res_sz)
    n <<= 1;
  n *= (res_sz + n - 1) / n, n >>= 1;
  For(i, n, n1 - 1) x[i - n].imag(x[i].real());
  For(i, n, n2 - 1) y[i - n].imag(y[i].real());
  x.resize(n), y.resize(n);
  auto res = poly_mul_mod(n, x, y, 1i);
  res.resize(res_sz);
  For(i, 0, min(n, res_sz - n) - 1) {
    res[i + n].real(res[i].imag()), res[i].imag(0);
  }
  return res;
}
il void Main() {
  int n, m;
  read(n, m);
  vector<Z> F(n + 1), G(m + 1);
  For(i, 0, n) {
    int x;
    read(x), F[i] = x;
  }
  For(i, 0, m) {
    int y;
    read(y), G[i] = y;
  }
  auto H = poly_mul(F, G);
  // cerr << "OK mul\n";
  For(i, 0, n + m) {
    printf("%lld%c", ll(round(H[i].real())), " \n"[i == n + m]);
  }
}
} // namespace

// signed main() { return Main(), 0; }

void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c) {
  vector<Z> A(n + 1), B(m + 1);
  For(i, 0, n) A[i].real(a[i]);
  For(i, 0, m) B[i].real(b[i]);
  auto C = poly_mul(A, B);
  For(i, 0, n + m) c[i] = round(C[i].real());
}

评测结果