代码

#include <cstdio>
#include <ctime>
#include <iostream>

// #define int long long

using u64 = uint64_t;

const int kMaxN = 4e5 + 5, kMod = 998244353, kG = 3, kInvG = 332748118;

template<class T>
T qpow(T bs, T idx, T kMod) {
  bs %= kMod;
  int ret = 1;
  for (; idx; idx >>= 1, bs = 1ll * bs * bs % kMod)
    if (idx & 1)
      ret = 1ll * ret * bs % kMod;
  return ret;
}
int inv(int x, int kMod) {
  x %= kMod;
  if (!x) { std::cerr << "inv error\n"; return 0; }
  return qpow(x, kMod - 2, kMod);
}

namespace Modular {
template<class T, const T kMod>
T add(T x, T y) {
  if (x + y >= kMod) return x + y - kMod;
  else return x + y;
}

template<class T, const T kMod>
T minu(T x, T y) {
  if (x - y < 0) return x - y + kMod;
  else return x - y;
}
} // namespace Modular

template<class T, const T kMod>
struct Mint {
// public:
  using u64 = unsigned long long;
  using u128 = __uint128_t;
  T m = kMod; u64 b = ((u128)1 << 64) / kMod;

  T x;

  Mint() { x = 0; }
  template<class _T> Mint(_T _x) { x = _x; }

  template <class _Tp>
  _Tp reduce(_Tp a) {
    u64 q = ((u128)a * b) >> 64;
    _Tp r = (u64)a - q * m;
    return r < m ? r : r - m;
  }

  friend Mint operator +(Mint m1, Mint m2) { return Mint(Modular::add<T, kMod>(m1.x, m2.x)); }
  friend Mint operator -(Mint m1, Mint m2) { return Mint(Modular::minu<T, kMod>(m1.x, m2.x)); }
  friend Mint operator *(Mint m1, Mint m2) { return Mint(m1.reduce((u64)m1.x * m2.x)); }
  friend Mint operator /(Mint m1, Mint m2) { return Mint(m1.reduce((u64)m1.x * inv(m2.x, kMod))); }
  // friend Mint operator +=(Mint &m1, Mint m2) { return m1 = m1 + m2; }
  // friend Mint operator -=(Mint &m1, Mint m2) { return m1 = m1 - m2; }
  // friend Mint operator *=(Mint &m1, Mint m2) { return m1 = m1 * m2; }
  // friend Mint operator /=(Mint &m1, Mint m2) { return m1 = m1 / m2; }
  Mint operator +=(Mint m2) { return x = Modular::add<T, kMod>(x, m2.x); }
  Mint operator -=(Mint m2) { return x = Modular::minu<T, kMod>(x, m2.x); }
  Mint operator *=(Mint m2) { return x = reduce((u64)x * m2.x); }
  Mint operator /=(Mint m2) { return x = reduce((u64)x * inv(m2.x, kMod)); }

  template<class _T> friend Mint operator +(Mint m1, _T m2) { return Mint(Modular::add<T, kMod>(m1.x, m2 % kMod)); }
  template<class _T> friend Mint operator -(Mint m1, _T m2) { return Mint(Modular::minu<T, kMod>(m1.x, m2 % kMod)); }
  template<class _T> friend Mint operator *(Mint m1, _T m2) { return Mint(m1.reduce((u64)m1.x * m2)); }
  template<class _T> friend Mint operator /(Mint m1, _T m2) { return Mint(m1.reduce((u64)m1.x * inv(m2, kMod))); }
  // template<class _T> friend Mint operator +=(Mint &m1, _T m2) { return m1 = m1 + m2; }
  // template<class _T> friend Mint operator -=(Mint &m1, _T m2) { return m1 = m1 - m2; }
  // template<class _T> friend Mint operator *=(Mint &m1, _T m2) { return m1 = m1 * m2; }
  // template<class _T> friend Mint operator /=(Mint &m1, _T m2) { return m1 = m1 / m2; }
  template<class _T> Mint operator +=(_T m2) { return x = Modular::add<T, kMod>(x, m2); }
  template<class _T> Mint operator -=(_T m2) { return x = Modular::minu<T, kMod>(x, m2); }
  template<class _T> Mint operator *=(_T m2) { return x = 1ll * x * m2 % kMod; }
  template<class _T> Mint operator /=(_T m2) { return x = 1ll * x * inv(m2, kMod) % kMod; }
  template<class _T> friend Mint operator +(_T m1, Mint m2) { return Mint(Modular::add<T, kMod>(m1 % kMod, m2.x)); }
  template<class _T> friend Mint operator -(_T m1, Mint m2) { return Mint(Modular::minu<T, kMod>(m1 % kMod, m2)); }
  template<class _T> friend Mint operator *(_T m1, Mint m2) { return Mint(1ll * m1 * m2.x % kMod); }
  template<class _T> friend Mint operator /(_T m1, Mint m2) { return Mint(1ll * m1 * inv(m2.x, kMod) % kMod); }
  friend Mint operator -(Mint &m1) { return Mint(m1.x == 0 ? (kMod - 1) : (m1.x - 1)); }
  friend Mint operator --(Mint &m1) { return m1 = Mint(m1.x == 0 ? (kMod - 1) : (m1.x - 1)); }
  friend Mint operator ++(Mint &m1) { return m1 = Mint(m1.x == (kMod - 1) ? 0 : (m1.x + 1)); }
  friend bool operator ==(Mint m1, Mint m2) { return m1.x == m2.x; }

  friend std::istream &operator >>(std::istream &is, Mint &m) {
    int x;
    is >> x;
    m = Mint(x);
    return is;
  }
  friend std::ostream &operator <<(std::ostream &os, Mint m) {
    os << m.x;
    return os;
  }
};

using mint = Mint<int, kMod>;

int n, m, len, c;
int rev[kMaxN];
mint a[kMaxN], b[kMaxN], g[kMaxN], ig[kMaxN];

int getlen(int n) {
  int ret = 1;
  for (; ret <= n; ret <<= 1, ++c) {}
  return ret;
}

void prework() {
  len = getlen(n + m + 1);
  mint gg = qpow(kG, (kMod - 1) / len, kMod), igg = qpow(kInvG, (kMod - 1) / len, kMod);
  g[0] = ig[0] = 1;
  for (int i = 1; i < len; ++i) {
    g[i] = g[i - 1] * gg;
    ig[i] = ig[i - 1] * igg;
    for (int j = 0; j < c; ++j)
      if (i >> j & 1)
        rev[i] |= (1 << c - j - 1);
    // std::cerr << i << ' ' << rev[i] << '\n';
  }
}

void ntt(mint *a, mint *g) {
  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) {
        mint tmp = a[i + j + m] * g[len / l * j];
        a[i + j + m] = a[i + j] - tmp;
        a[i + j] = a[i + j] + tmp;
      }
    }
  }
}

void dickdreamer() {
  std::cin >> n >> m;
  for (int i = 0; i <= n; ++i)
    std::cin >> a[i];
  for (int i = 0; i <= m; ++i)
    std::cin >> b[i];
  prework();
  ntt(a, g), ntt(b, g);
  for (int i = 0; i < len; ++i)
    a[i] *= b[i];
  ntt(a, ig);
  int invl = qpow(len, kMod - 2, kMod);
  for (int i = 0; i <= n + m; ++i)
    std::cout << a[i] * invl << ' ';
}

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' << std::endl;
  return 0;
}

评测结果