代码

// clang-format off
#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

#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

template <uint32_t mod> class mod_int {
private:
  static constexpr uint32_t get_r() {
    uint32_t ret = mod;
    for (int i = 0; i < 4; i++)
      ret *= 2 - mod * ret;
    return ret;
  }
  static constexpr uint32_t r = get_r();
  static constexpr uint32_t n2 = -uint64_t(mod) % mod;
  static_assert(r * mod == 1 && mod < (1 << 30) && mod & 1);
  uint32_t data;

public:
  constexpr mod_int() : data(0) {}
  template <class int_t>
  constexpr mod_int(const int_t x)
      : data(reduce(
            uint64_t((sizeof(int_t) < sizeof(uint32_t) ? x : x % int_t(mod)) +
                     mod) *
            n2)){};
  static constexpr uint32_t reduce(const uint64_t x) {
    return (x + uint64_t(uint32_t(x) * (-r)) * mod) >> 32;
  }
  constexpr mod_int &operator+=(const mod_int &r) {
    if (int32_t(data += r.data - 2 * mod) < 0) {
      data += 2 * mod;
    }
    return *this;
  }
  constexpr mod_int &operator-=(const mod_int &r) {
    if (int32_t(data -= r.data) < 0) {
      data += 2 * mod;
    }
    return *this;
  }
  constexpr mod_int &operator*=(const mod_int &r) {
    return data = reduce((uint64_t)data * r.data), *this;
  }
  constexpr mod_int &operator/=(const mod_int &r) { return *this *= r.inv(); }
  constexpr friend mod_int operator+(mod_int l, const mod_int &r) {
    return l += r;
  }
  constexpr friend mod_int operator-(mod_int l, const mod_int &r) {
    return l -= r;
  }
  constexpr friend mod_int operator*(mod_int l, const mod_int &r) {
    return l *= r;
  }
  constexpr friend mod_int operator/(mod_int l, const mod_int &r) {
    return l /= r;
  }
  constexpr mod_int operator-() const { return mod_int() - mod_int(*this); }
  template <class int_t> constexpr mod_int pow(int_t r) const {
    mod_int res(1), w(*this);
    for (; r; r >>= 1, w *= w)
      if (r & 1)
        res *= w;
    return res;
  }
  constexpr mod_int inv() const { return pow(mod - 2); }
  constexpr uint32_t value() const {
    uint32_t res = reduce(data);
    return res >= mod ? res - mod : res;
  }
};
template <const ll Mod> istream &operator>>(istream &istr, mod_int<Mod> &x) {
  ll _temp;
  istr >> _temp, x = _temp;
  return istr;
}
template <const ll Mod> ostream &operator<<(ostream &ostr, mod_int<Mod> x) {
  ostr << x.value();
  return ostr;
}

using Z = mod_int<998244353>;
constexpr Z operator""_Z(ull x);

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();
}

评测结果