代码

// clang-format off
#include <bits/stdc++.h>

using namespace std;

#define il inline
#define mkp make_pair
#define pii pair<int,int>
#define pll pair<long long, long long>
#define fi first
#define se second
#define lll __int128
#define ll long long
#define uint unsigned int
#define ull unsigned ll
#define db double
#define ldb long double
#define sq(x) ((x)*(x))
#define For(i,j,k) for(int i=(j); i<=(k); ++i) // NOLINT
#define ForDown(i,j,k) for(int i=(j); i>=(k); --i) // NOLINT
#define pb push_back
#define eb emplace_back
#define FileIO(filename) freopen(filename ".in" ,"r",stdin);freopen(filename ".out" ,"w",stdout)
template<typename T> 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...); }
#if __cplusplus < 201400
#warning "Please use c++14 or higher."
template<typename T> 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> il T qpow(T x, ull y){T ans=1;while(y){if(y&1)ans*=x;x*=x;y>>=1;}return ans;}
#else
template<typename T> il constexpr 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> il constexpr T qpow(T x, ull y){T ans=1;while(y){if(y&1)ans*=x;x*=x;y>>=1;}return ans;}
#endif

// File head end
// clang-format on

using u32 = uint32_t;
using u64 = uint64_t;

#define _always_inline __attribute__((always_inline))
#define _set_op(tp, op, attr)                                                  \
  attr tp operator op(const tp &rhs) const {                                   \
    tp lhs = *this;                                                            \
    return lhs op## = rhs;                                                     \
  }

template <u32 mod> class Modint {
  u32 _v;
  constexpr inline static u32 __get_inv_r(u32 x) {
    u32 y = x;
    y *= 2ull - x * y, y *= 2ull - x * y, y *= 2ull - x * y, y *= 2ull - x * y;
    return y;
  }
  _always_inline constexpr inline static u32 __shrk(u32 x) {
    return min(x, x - mod);
  }
  _always_inline constexpr inline static u32 __dilt(u32 x) {
    return min(x, x + mod);
  }
  _always_inline constexpr inline static u32 __reduce(u64 x) {
    return (x + u64(u32(x) * -mod_inv) * mod) >> 32;
  }

public:
  constexpr static inline u32 r2 = (1ull << 32) % mod * (1ull << 32) % mod,
                              mod_inv = __get_inv_r(mod);
  static_assert(mod && (mod < (1u << 31)) && (mod & 1));
  static_assert((mod_inv * mod) == 1u);
  static_assert(__reduce(r2) == (1ull << 32) % mod);

  constexpr Modint(u32 v = 0) : _v(__reduce(u64(v) * r2)) {}
  constexpr Modint &operator+=(Modint rhs) {
    return _v = __shrk(_v + rhs._v), *this;
  }
  constexpr Modint &operator-=(Modint rhs) {
    return _v = __dilt(_v - rhs._v), *this;
  }
  constexpr Modint &operator*=(Modint rhs) {
    return _v = __reduce(u64(_v) * rhs._v), *this;
  }
  constexpr Modint pow(u64 y) const {
    Modint ans = 1, x = *this;
    while (y) {
      if (y & 1)
        ans *= x;
      x *= x, y >>= 1;
    }
    return ans;
  }
  constexpr Modint inv() const { return this->pow(mod - 2); }
  constexpr u32 value() const { return __reduce(_v); }
  constexpr Modint &operator/=(Modint rhs) { return (*this) *= rhs.inv(); }
  _set_op(Modint, +, constexpr) _set_op(Modint, -, constexpr)
      _set_op(Modint, *, constexpr) _set_op(Modint, /, constexpr)
};

using Z = Modint<998244353>;

class Poly : public vector<Z> {
  il static constexpr Z G = 3;
  il static constexpr uint MAXN = 1u << 21;

  il static vector<uint> _Rev;
  il static uint cur_len = 0;
  il static bool gn_table_ok = 0;
  il static Z GN[MAXN];
  il static void init_rev(uint len) {
    cur_len = len;
    _Rev.resize(len);
    For(i, 0, len - 1) {
      _Rev[i] = _Rev[i >> 1] >> 1;
      if (i & 1)
        _Rev[i] |= len >> 1;
    }
  }
  il static void init_gn_table() {
    GN[21] = qpow(G, 998244352 / (1 << 21));
    for (uint l = MAXN >> 1, i = 20; l >= 2; l >>= 1, i--) {
      GN[i] = sq(GN[i + 1]);
    }
    gn_table_ok = 1;
  }

  il void NTT(uint len, bool tp, Poly &res) const {
    res = *this;
    res.resize(len);
    if (len != cur_len)
      init_rev(len);
    if (!gn_table_ok)
      init_gn_table();
    for (uint i = 0; i < len; i++)
      if (i < _Rev[i])
        ::swap(res[i], res[_Rev[i]]);
    for (uint l = 2, lg = 1; l <= len; l <<= 1, lg++) {
      uint m = l >> 1;
      Z gn = GN[lg];
      for (uint i = 0; i < len; i += l) {
        Z g = 1;
        for (uint j = 0; j < m; j++, g *= gn) {
          Z tmp = res[i + j + m] * g;
          res[i + j + m] = res[i + j] - tmp;
          res[i + j] += tmp;
        }
      }
    }
    if (!tp) {
      reverse(res.begin() + 1, res.begin() + len);
      auto inv = Z(len).inv();
      For(i, 0, len - 1) res[i] *= inv;
    }
  }

public:
  static il Poly dot_mul(const Poly &x, const Poly &y) {
    Poly res = x;
    if (y.size() < x.size())
      res.resize(y.size());
#pragma GCC unroll(4)
    For(i, 0, signed(res.size()) - 1) res[i] *= y[i];
    return res;
  }
  Poly() = default;
  Poly(int sz) { this->clear(), this->resize(sz); }
  Poly inv() const { Poly res = 1; }
  void operator+=(const Poly &rhs) {
    int n_sz = max(this->size(), rhs.size()), rhs_sz = rhs.size(); // NOLINT
    this->resize(n_sz);
#pragma GCC unroll(4)
    For(i, 0, rhs_sz - 1) this->operator[](i) += rhs[i];
  }
  void operator-=(const Poly &rhs) {
    int n_sz = max(this->size(), rhs.size()), rhs_sz = rhs.size(); // NOLINT
    this->resize(n_sz);
#pragma GCC unroll(4)
    For(i, 0, rhs_sz - 1) operator[](i) -= rhs[i];
  }
  void operator*=(const Poly &rhs) {
    int N = 1, NN = this->size() + rhs.size() - 1; // NOLINT
    while (N < NN)
      N <<= 1;
    Poly x, y;
    this->NTT(N, 1, x), rhs.NTT(N, 1, y);
    Poly ans = dot_mul(x, y);
    ans.NTT(N, 0, *this);
    resize(NN);
  }
#define setOper(x)                                                             \
  [[nodiscard]] Poly operator x(const Poly &rhs) const {                       \
    auto lhs = *this;                                                          \
    lhs x## = rhs;                                                             \
    return lhs;                                                                \
  }
  setOper(+) setOper(-) setOper(*)
#undef setOper
};

Poly A, B;

void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c) {
  A.resize(n + 1), B.resize(m + 1);
  copy(a, a + 1 + n, A.begin());
  copy(b, b + 1 + m, B.begin());
  A *= B;
  For(i, 0, n + m) c[i] = A[i].value();
}

评测结果