代码

#include <bits/stdc++.h>

class Poly {
protected:
  typedef unsigned int value_t;
  typedef unsigned int size_t;
  typedef unsigned long long int cast_t;
  typedef value_t *ptr_t;
  static const size_t BUFFER_SIZE = 1ULL << 21;
  typedef value_t arr_t[BUFFER_SIZE];

private:
  static arr_t ROOT, INV;
  ptr_t first, last, end_of_storage;

  static size_t get_len(size_t x) {
    size_t len = 1;
    while (len < x) len <<= 1;
    return len;
  }
  static value_t qpow(value_t x, value_t y) {
    value_t res = 1;
    for (; y; y >>= 1, x = static_cast<cast_t>(x) * x % P)
      if (y & 1) res = static_cast<cast_t>(res) * x % P;
    return res;
  }
  static value_t mod_inv(value_t x) { return qpow(x, P - 2); }
  static void init_unit_roots(size_t n) {
    static size_t lim = 1;
    if (lim < n) {
      size_t l = n >> 1;
      value_t g = qpow(G, (P - 1) / n);
      ROOT[l] = 1;
      for (size_t i = l + 1; i < n; ++i) ROOT[i] = static_cast<cast_t>(ROOT[i - 1]) * g % P;
      for (size_t i = l - 1; i >= lim; --i) ROOT[i] = ROOT[i << 1];
      lim = n;
    }
  }
  static void init_inv(size_t n) {
    static size_t lim = 0;
    if (lim < n) {
      INV[1] = 1;
      for (size_t i = (lim < 2 ? 2 : lim); i < n; ++i)
        INV[i] = static_cast<cast_t>(P - P / i) * INV[P % i] % P;
    }
  }
  static value_t legendre_symbol(value_t x) { return x == 0 ? 0 : qpow(x, P - 1 >> 1); }
  static value_t tonelli_shanks(value_t a) {
    if (legendre_symbol(a) != 1) return 0;
    value_t q = P - 1, t = 0, n, z; // P = q * 2 ^ t + 1
    while (!(q & 1)) q >>= 1, ++t;
    if (t == 1) return qpow(a, P + 1 >> 2);
    for (n = 1; n < P; ++n)
      if (legendre_symbol(n) == P - 1) {
        z = qpow(n, q);
        break;
      }
    value_t y = z, r = t, x = qpow(a, q - 1 >> 1), b = x;
    x = static_cast<cast_t>(x) * a % P, b = static_cast<cast_t>(x) * b % P;
    while (1) {
      if (b == 1) return x < P - x ? x : P - x;
      value_t m;
      for (m = 1; m < r; ++m)
        if (qpow(b, 1ULL << m) == 1) break;
      value_t v = qpow(y, 1ULL << r - m - 1);
      y = static_cast<cast_t>(v) * v % P, r = m, x = static_cast<cast_t>(x) * v % P,
      b = static_cast<cast_t>(b) * y % P;
    }
  }
  Poly &dif_fft_core() {
    init_unit_roots(size());
    for (size_t n = size(), i = n; i >= 2; i >>= 1)
      for (size_t j = 0, l = i >> 1; j < n; j += i)
        for (size_t k = 0; k < l; ++k) {
          value_t u = *(first + j + k), v = *(first + j + k + l);
          *(first + j + k) = (static_cast<cast_t>(u) + v) % P;
          *(first + j + k + l) = (static_cast<cast_t>(u) + P - v) * ROOT[l + k] % P;
        }
    return *this;
  }
  Poly &dit_fft_core() {
    for (size_t n = size(), i = 2; i <= n; i <<= 1)
      for (size_t j = 0, l = i >> 1; j < n; j += i)
        for (size_t k = 0; k < l; ++k) {
          value_t u = *(first + j + k),
                  v = static_cast<cast_t>(ROOT[l + k]) * *(first + j + k + l) % P;
          *(first + j + k) = (static_cast<cast_t>(u) + v) % P;
          *(first + j + k + l) = (static_cast<cast_t>(u) + P - v) % P;
        }
    return *this;
  }
  Poly &revbin() {
    for (size_t n = size(), i = 0, j = 0; i < n; ++i) {
      if (i < j) {
        value_t t = *(first + i);
        *(first + i) = *(first + j), *(first + j) = t;
      }
      for (size_t k = n >> 1; (j ^= k) < k; k >>= 1) {
      }
    }
    return *this;
  }
  Poly &reverse(ptr_t x, ptr_t y) {
    value_t t;
    while (y - x > 0) t = *x, *x++ = *--y, *y = t;
    return *this;
  }

public:
  typedef ptr_t iterator;
  static const value_t P = 998244353, G = 3;

  iterator begin() const { return first; }
  iterator end() const { return last; }
  size_t size() const { return last - first; }
  size_t capacity() const { return end_of_storage - first; }
  bool empty() const { return first == last; }
  Poly &resize(size_t new_size) {
    if (new_size > capacity()) {
      size_t old_capacity = capacity(), new_capacity = get_len(new_size);
      first = static_cast<ptr_t>(realloc(first, sizeof(value_t) * new_capacity));
      assert(first != NULL);
      end_of_storage = first + new_capacity;
      memset(first + old_capacity, 0, sizeof(value_t) * (new_capacity - old_capacity));
    } else if (size() > new_size)
      memset(first + new_size, 0, sizeof(value_t) * (size() - new_size));
    return last = first + new_size, *this;
  }
  value_t &operator[](size_t x) { return *(first + x); }
  value_t operator[](size_t x) const { return *(first + x); }
  Poly &dft(size_t len) { return resize(len).dif_fft_core(); }
  Poly &idft(size_t len) {
    resize(len).dit_fft_core().reverse(first + 1, last);
    value_t in = P - (P - 1) / len;
    for (ptr_t i = first; i != last; ++i) *i = static_cast<cast_t>(*i) * in % P;
    return *this;
  }
  Poly(size_t reserved = 1)
      : first(static_cast<ptr_t>(calloc(get_len(reserved), sizeof(value_t)))),
        last(first + reserved), end_of_storage(first + get_len(reserved)) {
    assert(reserved > 0 && first != NULL);
  }
  Poly(value_t const *start, value_t const *finish)
      : first(static_cast<ptr_t>(malloc(get_len(finish - start) * sizeof(value_t)))),
        last(first + (finish - start)), end_of_storage(first + get_len(finish - start)) {
    assert(first != NULL);
    memcpy(first, start, sizeof(value_t) * (finish - start));
    memset(last, 0, sizeof(value_t) * (end_of_storage - last));
  }
  Poly(const Poly &rhs) : Poly(rhs.first, rhs.last) {}
  Poly(std::initializer_list<value_t> l) : Poly(l.begin(), l.end()) {}
  ~Poly() { free(first); }
  Poly copy() const { return Poly(*this); }
  Poly slice(value_t const *start, value_t const *finish) const { return Poly(start, finish); }
  Poly &operator=(const Poly &rhs) {
    return resize(rhs.size()), memcpy(first, rhs.first, sizeof(value_t) * rhs.size()), *this;
  }
  Poly operator-() const {
    Poly res(*this);
    for (ptr_t i = res.first; i != res.last; ++i)
      if (*i != 0) *i = P - *i;
    return res;
  }
  Poly operator~() const {
    size_t n = size(), len = get_len(n);
    assert(*first != 0);
    Poly res(len << 1);
    res[0] = mod_inv(*first);
    for (size_t i = 2; i <= len; i <<= 1) {
      size_t l = i << 1;
      Poly cpy = slice(first, first + i).dft(l);
      res.dft(l);
      for (size_t j = 0; j < l; ++j)
        res[j] =
            static_cast<cast_t>(res[j]) * (2 + P - static_cast<cast_t>(cpy[j]) * res[j] % P) % P;
      res.idft(l).resize(i);
    }
    return res.resize(n);
  }
  Poly &operator+=(const Poly &rhs) {
    if (size() < rhs.size()) resize(rhs.size());
    for (size_t i = 0, len = rhs.size(); i < len; ++i)
      *(first + i) = (static_cast<cast_t>(*(first + i)) + *(rhs.first + i)) % P;
    return *this;
  }
  Poly &operator-=(const Poly &rhs) {
    if (size() < rhs.size()) resize(rhs.size());
    for (size_t i = 0, len = rhs.size(); i < len; ++i)
      *(first + i) = (static_cast<cast_t>(*(first + i)) + P - *(rhs.first + i)) % P;
    return *this;
  }
  Poly &operator*=(Poly rhs) {
    size_t n = size(), m = rhs.size(), len = get_len(n + m - 1);
    dft(len), rhs.dft(len);
    for (size_t i = 0; i < len; ++i)
      *(first + i) = (static_cast<cast_t>(*(first + i)) * *(rhs.first + i)) % P;
    return idft(len).resize(n + m - 1);
  }
  Poly &operator/=(Poly rhs) {
    assert(size() >= rhs.size());
    size_t n = size() - rhs.size() + 1;
    reverse(first, last), reverse(rhs.first, rhs.last);
    return (*this *= ~(rhs.resize(n))).resize(n).reverse(first, last);
  }
  Poly &operator%=(const Poly &rhs) {
    return (*this -= (*this / rhs) * rhs).resize(rhs.size() - 1);
  }
  Poly &derivative() {
    assert(size() >= 2);
    for (size_t i = 1, len = size(); i < len; ++i)
      *(first + i - 1) = static_cast<cast_t>(*(first + i)) * i % P;
    return *(--last) = 0, *this;
  }
  Poly &integral() {
    init_inv(size());
    for (size_t i = size() - 1; i > 0; --i)
      *(first + i) = static_cast<cast_t>(*(first + i - 1)) * INV[i] % P;
    return *first = 0, *this;
  }
  Poly ln() const {
    assert(*first == 1);
    return (copy().derivative() * ~(*this)).resize(size()).integral();
  }
  Poly exp() const {
    assert(*first == 0);
    size_t n = size(), len = get_len(n);
    Poly res(len << 1);
    res[0] = 1;
    for (size_t i = 2; i <= len; i <<= 1)
      res *= slice(first, first + i) - res.resize(i).ln() + Poly{1};
    return res.resize(n);
  }
  Poly sqrt() const {
    assert(legendre_symbol(*first) == 1);
    size_t n = size(), len = get_len(n);
    Poly res(len << 1);
    res[0] = tonelli_shanks(*first);
    value_t inv2 = (P >> 1) + 1;
    for (size_t i = 2; i <= len; i <<= 1) {
      size_t l = i << 1;
      Poly cpy = slice(first, first + i).dft(l), ires = (~res.resize(i)).dft(l);
      res.dft(l);
      for (size_t j = 0; j < l; ++j)
        res[j] = inv2 * (res[j] + static_cast<cast_t>(ires[j]) * cpy[j] % P) % P;
      res.idft(l).resize(i);
    }
    return res.resize(n);
  }
  Poly pow(value_t k) const {
    Poly res = ln();
    for (ptr_t i = res.first; i != res.last; ++i) *i = static_cast<cast_t>(*i) * k % P;
    return res.exp();
  }
  Poly evaluate(const Poly &points) const {
    std::vector<Poly> vp(points.size() << 2);
    std::function<void(size_t, value_t const *, value_t const *)> build =
        [&build, &vp](size_t pos, value_t const *start, value_t const *finish) {
          if (start == finish) {
            vp[pos] = Poly{P - *start, 1};
          } else {
            value_t const *mid = start + (finish - start >> 1);
            build(pos << 1, start, mid), build(pos << 1 | 1, mid + 1, finish);
            vp[pos] = vp[pos << 1] * vp[pos << 1 | 1];
          }
        };
    build(1, points.first, points.last - 1);
    Poly res(points.size());
    res.last = res.first;
    std::function<void(size_t, value_t const *, value_t const *, const Poly &)> solve =
        [&solve, &vp, &res](size_t pos, value_t const *start, value_t const *finish,
                            const Poly &r) {
          if (start == finish) {
            *(res.last++) = *(r.first);
          } else {
            value_t const *mid = start + (finish - start >> 1);
            solve(pos << 1, start, mid, r % vp[pos << 1]),
                solve(pos << 1 | 1, mid + 1, finish, r % vp[pos << 1 | 1]);
          }
        };
    solve(1, points.first, points.last - 1, size() > points.size() ? *this % vp[1] : *this);
    return res;
  }
  friend Poly operator+(const Poly &lhs, const Poly &rhs) { return Poly(lhs) += rhs; }
  friend Poly operator-(const Poly &lhs, const Poly &rhs) { return Poly(lhs) -= rhs; }
  friend Poly operator*(const Poly &lhs, const Poly &rhs) { return Poly(lhs) *= rhs; }
  friend Poly operator/(const Poly &lhs, const Poly &rhs) { return Poly(lhs) /= rhs; }
  friend Poly operator%(const Poly &lhs, const Poly &rhs) { return Poly(lhs) %= rhs; }
  friend void swap(Poly &lhs, Poly &rhs) {
    ptr_t t;
    t = lhs.first, lhs.first = rhs.first, rhs.first = t;
    t = lhs.last, lhs.last = rhs.last, rhs.last = t;
    t = lhs.end_of_storage, lhs.end_of_storage = rhs.end_of_storage, rhs.end_of_storage = t;
  }
};

unsigned int Poly::ROOT[1ULL << 21], INV[1ULL << 21];

struct IO {
  char a[1 << 25], *s;
  char b[1 << 25], *t;
  IO() : s(a), t(b) {
#ifdef LOCAL
    freopen("..\\in", "r", stdin), freopen("..\\out", "w", stdout);
#endif
    a[fread(a, 1, sizeof a, stdin)] = 0;
  }
  ~IO() { fwrite(b, 1, t - b, stdout); }
  template <typename T> IO &operator>>(T &x) {
    x = 0;
    while (*s < '0') ++s;
    while (*s > ' ') x = x * 10 + *s++ - '0';
    return *this;
  }
  IO &operator<<(char x) { return *t++ = ' ', *this; }
  template <typename T> IO &operator<<(T x) {
    static char c[24];
    char *i = c;
    if (!x) {
      *t++ = '0';
    } else {
      while (x) {
        T y = x / 10;
        *i++ = x - y * 10 + '0', x = y;
      }
      while (i != c) *t++ = *--i;
    }
    return *this;
  }
} io;

using namespace std;
int main() {
#ifdef LOCAL
  freopen("..\\in", "r", stdin), freopen("..\\out", "w", stdout);
#endif
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  io >> n >> m;
  Poly a(n + 1), b(m + 1);
  for (auto &i : a) io >> i;
  for (auto &i : b) io >> i;
  for (auto i : a *b) io << i << '\n';
  return 0;
}

评测结果