代码

// GENERATE DATE: 2024-02-29 02:21:56.087411


// GENERATE FROM: https://github.com/rogeryoungh/algorithm-cpp
#include <type_traits>
#include <cstdint>

using i8 = std::int8_t;
using i16 = std::int16_t;
using i32 = std::int32_t;
using i64 = std::int64_t;
using i128 = __int128_t;
using u8 = std::uint8_t;
using u16 = std::uint16_t;
using u32 = std::uint32_t;
using u64 = std::uint64_t;
using u128 = __uint128_t;
using usize = std::size_t;
using f32 = float;
using f64 = double;
using f80 = long double;

template<class T>
struct type_identity { using type = T; };

template <class T>
using TI = typename type_identity<T>::type;

#include <cstdio>
#include <vector>

struct FreadBuf {
  std::FILE *const f;
  std::vector<u8> buf;
  const u8 *p, *end;
  usize read_cnt = 0;
  FreadBuf(std::FILE *const f, usize size) : f(f), buf(size) {
    p = buf.data(), end = p + size - 8;
    read_cnt = std::fread(buf.data(), 1, end - p, f);
    buf[read_cnt] = 0;
  }
  void load() {
    u8 *p2 = std::move(p, end, buf.data());
    read_cnt = std::fread(p2, 1, end - p2, f);
    p2[read_cnt] = 0, p = buf.data();
  }
  bool eof() const {
    return read_cnt == 0;
  }
  void reserve(usize n) {
    if (end - p < i64(n))
      load();
  }
  u8 top() const {
    return *p;
  }
  u8 pop() {
    return *p++;
  }
};



#include <cstring>
#include <vector>

struct AtoiHelper {
  std::vector<u16> pre;
  AtoiHelper() : pre(0x10000, -1) {
    for (u32 i = 0; i != 0x100; ++i) {
      for (u32 j = 0; j != 10; ++j) {
        u32 t = i * 0x100 | j | 0x30;
        if ('0' <= i && i <= '9')
          pre[t] = j * 10 + i - 0x30;
        else
          pre[t] = j | 0x100;
      }
    }
  }
  u64 getu(u8 c, const u8 *&p0) {
    const u8 *p = p0;
    u64 x = c & 0xf;
    while (true) {
      u16 t;
      std::memcpy(&t, p, 2);
      auto ft = pre[t];
      p += 2;
      if (ft < 100) { // len = 2
        x = x * 100 + ft;
      } else { // len = 1
        if (ft < 0x1000)
          x = x * 10 + ft - 0x100;
        else
          --p;
        break;
      }
    }
    return p0 = p, x;
  }
};


template <class Buf>
struct Reader {
  Buf buf;
  AtoiHelper atoi;
  Reader(std::FILE *f, usize size = 1 << 18) : buf(f, size) {}
  bool eof() const {
    return buf.eof();
  }
  template <class T>
  Reader &operator>>(T &x) {
    while (true) {
      buf.reserve(0x40);
      u8 c = buf.pop();
      if (std::is_signed_v<T> && c == '-') {
        x = -T(atoi.getu(0, buf.p));
        break;
      }
      if ('0' <= c && c <= '9') {
        x = atoi.getu(c, buf.p);
        break;
      }
    }
    return *this;
  }
};



#include <array>

struct ItoaHelper {
  std::vector<u32> pre;
  ItoaHelper() : pre(10000) {
    for (u32 i = 0; i < 10000; ++i) {
      u32 ti = i;
      for (u32 j = 0; j != 4; ++j) {
        pre[i] = pre[i] << 8 | ti % 10 | 0x30;
        ti /= 10;
      }
    }
  }
  void putu(u64 x, u8 *&p) {
    std::array<u8, 32> tmp;
    u8 *s0 = tmp.data() + 30, *s1 = s0;
    while (x >= 10000) {
      std::memcpy(s0 -= 4, &pre[x % 10000], 4);
      x /= 10000;
    }
    std::memcpy(s0 -= 4, &pre[x % 10000], 4);
    s0 += x < 100 ? (x < 10 ? 3 : 2) : (x < 1000 ? 1 : 0);
    p = std::copy(s0, s1, p);
  }
};

#include <cassert>

template <u8 endc = 0>
struct Writer {
  std::FILE *const f;
  std::vector<u8> buf;
  ItoaHelper itoa;
  u8 *p, *end;
  Writer(std::FILE *const f, usize size = 1 << 18) : f(f), buf(size) {
    assert(size >= 0x100);
    p = buf.data(), end = p + size;
  }
  ~Writer() {
    flush();
  }
  void flush() {
    std::fwrite(buf.data(), 1, p - buf.data(), f);
    p = buf.data();
  }
  void reserve(usize n) {
    if (end - p < i64(n))
      flush();
  }
  template <class T>
  Writer &operator<<(T x) {
    reserve(0x40);
    if (std::is_signed_v<T> && x < 0) {
      *p++ = '-';
      itoa.putu(-x, p);
    } else {
      itoa.putu(x, p);
    }
    if constexpr (endc != 0)
      *p++ = endc;
    return *this;
  }
  Writer &operator<<(char x) {
    *p++ = x;
    return *this;
  }
};


u32 countr_zero(u32 x) {
  return x == 0 ? 32 : __builtin_ctz(x);
}

u32 countr_one(u32 x) {
  return countr_zero(~x);
}

template <class U>
struct Mont {
  using S = std::make_signed_t<U>;
  using UU = std::conditional_t<std::is_same_v<U, u32>, u64, u128>;
  const U MOD, MOD2, R, IR, R2, ONE;
  explicit constexpr Mont(U mod)
      : MOD(mod), MOD2(mod * 2), R(getR(mod)), IR(-getNR(mod)), R2(UU(R) * R % MOD), ONE(trans(1)) {
  }
  constexpr static U getR(U mod) {
    return (UU(1) << (sizeof(U) * 8)) % mod;
  }
  constexpr static U getNR(U mod) {
    U x = 1;
    for (u32 i = 0; i != 6; ++i)
      x *= 2 - x * mod;
    return x;
  }
  constexpr U trans(U x) const {
    // return (u64(x) << 32) % MOD;
    return reduce(UU(x) * R2);
  }
  constexpr U reduce(UU x) const {
    return (x + UU(U(x) * IR) * MOD) >> (sizeof(U) * 8);
  }
  constexpr U norm(U v) const {
    U v2 = v - MOD;
    return S(v2) < 0 ? v : v2;
  }
  constexpr U add(U a, U b) const {
    U v1 = a + b, v2 = v1 - MOD2;
    return S(v2) < 0 ? v1 : v2;
  }
  constexpr U sub(U a, U b) const {
    U v1 = a - b, v2 = v1 + MOD2;
    return S(v1) >= 0 ? v1 : v2;
  }
  constexpr U mul(U a, U b) const {
    return reduce(UU(a) * b);
  }
  constexpr U qpow(U a, u64 n, U r) const {
    for (; n > 0; n /= 2) {
      if (n % 2 == 1)
        r = mul(r, a);
      a = mul(a, a);
    }
    return r;
  }
  constexpr U qpow(U a, u64 n) const {
    return qpow(a, n, ONE);
  }
  constexpr U inv(U x) const {
    return qpow(x, MOD - 2);
  }
  constexpr U div(U a, U b) const {
    return reduce(qpow(b, MOD - 2, a));
  }
  constexpr U get(U x) const {
    return norm(reduce(x));
  }
  constexpr U div2(U x) const {
    return (x % 2 == 1 ? x + MOD : x) >> 1;
  }
  constexpr bool cmp(U a, U b) const {
    return get(a) == get(b);
  }
  constexpr bool ncmp(U a, U b) const {
    return !cmp(a, b);
  }
  constexpr U neg(U x) const {
    return x != 0 ? MOD2 - x : 0;
  }
};
using Mont32 = Mont<u32>;
using Mont64 = Mont<u64>;
template <class ModT>
using ModU = ModT::U;
template <class ModT>
using ModUU = ModT::UU;

template <class U>
struct NTTOriginalRadix2 {
  const Mont<U> _M;
  std::array<U, 64> rt{}, irt{}, rate2{}, irate2{};
  NTTOriginalRadix2(Mont<U> M, TI<U> G) : _M(std::move(M)) {
    const u32 rank2 = std::countr_zero(M.MOD - 1);
    rt[rank2] = M.qpow(M.trans(G), (M.MOD - 1) >> rank2);
    irt[rank2] = M.inv(rt[rank2]);
    for (u32 i = rank2; i != 0; --i) {
      rt[i - 1] = M.mul(rt[i], rt[i]);
      irt[i - 1] = M.mul(irt[i], irt[i]);
    }
    U prod = M.ONE, iprod = M.ONE;
    for (u32 i = 0; i != rank2 - 1; ++i) {
      rate2[i] = M.mul(prod, rt[i + 2]);
      irate2[i] = M.mul(iprod, irt[i + 2]);
      prod = M.mul(prod, irt[i + 2]);
      iprod = M.mul(iprod, rt[i + 2]);
    }
  }
  void ntt(U *f, usize n) {
    const auto M = _M;
    for (u32 l = n / 2; l >= 1; l /= 2) {
      U *fx = f, *fy = fx + l;
      for (u32 j = 0; j != l; ++j) {
        U x = fx[j], y = fy[j];
        fx[j] = M.add(x, y);
        fy[j] = M.sub(x, y);
      }
      U r = rate2[0];
      for (u32 i = l * 2, k = 1; i != n; i += l * 2, ++k) {
        fx = f + i, fy = fx + l;
        for (u32 j = 0; j != l; ++j) {
          U x = fx[j], y = M.mul(fy[j], r);
          fx[j] = M.add(x, y);
          fy[j] = M.sub(x, y);
        }
        r = M.mul(r, rate2[std::countr_one(k)]);
      }
    }
  }
  void intt(U *f, usize n) {
    const auto M = _M;
    U ivn = M.trans(M.MOD - (M.MOD - 1) / n);
    for (u32 l = 1; l <= n / 2; l *= 2) {
      U *fx = f, *fy = fx + l;
      for (u32 j = 0; j != l; ++j) {
        U x = fx[j], y = fy[j];
        if (l == n / 2)
          x = M.mul(x, ivn), y = M.mul(y, ivn); // div n here !!!
        fx[j] = M.add(x, y);
        fy[j] = M.sub(x, y);
      }
      U r = irate2[0];
      for (u32 i = l * 2, k = 1; i != n; i += l * 2, ++k) {
        fx = f + i, fy = fx + l;
        for (u32 j = 0; j != l; ++j) {
          U x = fx[j], y = fy[j];
          fx[j] = M.add(x, y);
          fy[j] = M.mul(M.sub(x, y), r);
        }
        r = M.mul(r, irate2[std::countr_one(k)]);
      }
    }
  }
  void conv(U *f, U *g, u32 n) {
    const auto M = _M;
    ntt(f, n);
    if (f != g)
      ntt(g, n);
    for (u32 i = 0; i != n; ++i)
      f[i] = M.mul(f[i], g[i]);
    intt(f, n);
  }
};

u32 bit_ceil(u32 x) {
  u32 t = 1;
  while (t < x)
   t *= 2;
  return t;
}

i32 main() {
  Reader<FreadBuf> fin(stdin);
  Writer<' '> fout(stdout);
  u32 n, m;
  fin >> n >> m;
  n++, m++;
  const u32 L = bit_ceil(n + m - 1);
  const auto M = Mont32{998244353};
  NTTOriginalRadix2 ntt(M, 3);
  std::vector<u32> f(L), g(L);
  for (u32 i = 0; i != n; ++i)
    fin >> f[i];
  for (u32 i = 0; i != m; ++i)
    fin >> g[i];
  ntt.conv(f.data(), g.data(), L);
  for (u32 i = 0; i != n + m - 1; ++i)
    fout << f[i];
  return 0;
}

评测结果