代码

#include <cstdio>
#include <iostream>
#include <vector>

// #define int int64_t

using i64 = int64_t;

const int kMaxN = 4e5 + 5, kMod = 998244353;

int len, rev[kMaxN], g[kMaxN], ig[kMaxN];

int qpow(int bs, int idx = kMod - 2) {
  int ret = 1;
  for (; idx; idx >>= 1, bs = (i64)bs * bs % kMod)
    if (idx & 1)
      ret = (i64)ret * bs % kMod;
  return ret;
}

inline int add(int x, int y) {
  return (x + y >= kMod ? x + y - kMod : x + y);
}

inline int sub(int x, int y) {
  return (x >= y ? x - y : x - y + kMod);
}

void prework(int n) {
  int c = 0;
  for (len = 1; len <= n; len <<= 1, ++c) {}
  int gg = qpow(3, (kMod - 1) / len), igg = qpow(gg);
  g[0] = ig[0] = 1;
  for (int i = 1; i < len; ++i) {
    g[i] = (i64)g[i - 1] * gg % kMod;
    ig[i] = (i64)ig[i - 1] * igg % kMod;
    rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (c - 1));
  }
}

struct Poly : std::vector<int> {
  friend Poly operator -(Poly a) {
    static Poly c;
    c.resize(a.size());
    for (int i = 0; i < c.size(); ++i)
      c[i] = sub(0, c[i]);
    return c;
  }
  friend Poly operator +(Poly a, Poly b) {
    static Poly c;
    c.resize(std::max(a.size(), b.size()));
    for (int i = 0; i < c.size(); ++i)
      c[i] = add(a[i], b[i]);
    return c;
  }
  friend Poly operator -(Poly a, Poly b) {
    static Poly c;
    c.resize(std::max(a.size(), b.size()));
    for (int i = 0; i < c.size(); ++i)
      c[i] = sub(a[i], b[i]);
    return c;
  }
  friend void ntt(Poly &a, int len, int *g) {
    if (a.size() < len) a.resize(len);
    for (int i = 0; i < len; ++i)
      if (i < rev[i])
        std::swap(a[i], a[rev[i]]);
    for (int l = 2; l <= len; l <<= 1) {
      int m = l / 2;
      for (int i = 0; i < len; i += l) {
        for (int j = 0; j < m; ++j) {
          int tmp = (i64)a[i + j + m] * g[len / l * j] % kMod;
          a[i + j + m] = sub(a[i + j], tmp);
          a[i + j] = add(a[i + j], tmp);
        }
      }
    }
  }
  friend Poly operator *(Poly a, Poly b) {
    int n = a.size() + b.size() - 1;
    ntt(a, len, g), ntt(b, len, g);
    for (int i = 0; i < len; ++i)
      a[i] = (i64)a[i] * b[i] % kMod;
    ntt(a, len, ig);
    int invl = qpow(len);
    for (int i = 0; i < len; ++i)
      a[i] = (i64)a[i] * invl % kMod;
    a.resize(n);
    return a;
  }
  friend void operator *=(Poly &a, Poly b) {
    int n = a.size() + b.size() - 1;
    ntt(a, len, g), ntt(b, len, g);
    for (int i = 0; i < len; ++i)
      a[i] = (i64)a[i] * b[i] % kMod;
    ntt(a, len, ig);
    int invl = qpow(len);
    for (int i = 0; i < len; ++i)
      a[i] = (i64)a[i] * invl % kMod;
    a.resize(n);    
  }
};

void dickdreamer() {
  int n, m;
  Poly a, b;
  std::cin >> n >> m;
  a.resize(n + 1), b.resize(m + 1);
  prework(n + m + 1);
  for (auto &x : a) std::cin >> x;
  for (auto &x : b) std::cin >> x;
  a *= b;
  for (auto x : a) std::cout << x << ' ';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}

评测结果