代码

// 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(register int i=(j); i<=(k); ++i) // NOLINT
#define ForDown(i,j,k) for(register 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

#ifndef ONLINE_JUDGE
  #define __lg log2
  namespace _Debug {
	  template <typename T> inline void _debug(const char* format, T t) { cerr<<format<<'='<<t<<endl; }
	  template <class First, class... Rest> inline void _debug(const char* format, First first, Rest... rest) { while (*format != ',') cerr << *format++; cerr << '=' << first << ","; _debug(format + 1, rest...);}
	  template <typename T> ostream& operator<<(ostream& os, const vector<T>& V) { os << "[ "; for (const auto& vv : V) os << vv << ", "; os << "]"; return os; }
	  #define debug(...) cerr<<"Line "<<__LINE__<<": ",_debug(#__VA_ARGS__, __VA_ARGS__);
  };
  using namespace _Debug;
#endif

// File head end
// clang-format on
namespace Modint {
template <const uint Mod> class Modint {
  uint _val;
  il static unordered_map<uint, uint> _inv;

public:
  Modint() : _val(0) {}
  constexpr Modint(ll val) : _val((val % Mod + Mod) % Mod) {}
  [[nodiscard]] il uint value() const { return _val; }
  [[nodiscard]] il uint inv() const {
    return _inv.count(_val) ? _inv[_val]
                            : _inv[_val] = qpow(*this, Mod - 2)._val;
  }
  void operator*=(const Modint &rhs) { _val = ((ull)_val * rhs._val) % Mod; }
  void operator/=(const Modint &rhs) { _val = ((ull)_val * rhs.inv()) % Mod; }
  void operator+=(const Modint &rhs) {
    int(_val += rhs._val - (Mod << 1)) < 0 ? _val += (Mod << 1) : (ull){};
  }
  void operator-=(const Modint &rhs) {
    int(_val -= rhs._val) < 0 ? _val += (Mod << 1) : (ull){};
  }
#define setOper(x)                                                             \
  [[nodiscard]] Modint operator x(const Modint &rhs) const {                   \
    auto lhs = *this;                                                          \
    lhs x## = rhs;                                                             \
    return lhs;                                                                \
  }
  setOper(+) setOper(-) setOper(*) setOper(/)
#undef setOper
};
template <const ll Mod> istream &operator>>(istream &istr, Modint<Mod> &x) {
  ll _temp;
  istr >> _temp, x = _temp;
  return istr;
}
template <const ll Mod> ostream &operator<<(ostream &ostr, Modint<Mod> x) {
  ostr << x.value();
  return ostr;
}
} // namespace Modint

using Z = Modint::Modint<998244353>;
constexpr Z operator""_Z(ull x) { return {(ll)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:
  Poly() = default;
  Poly(int sz) { this->clear(), this->resize(sz); }
  void operator+=(const Poly &rhs) {
    int n_sz = max(this->size(), rhs.size()), rhs_sz = rhs.size(); // NOLINT
    this->resize(n_sz);
    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);
    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;
    static Poly x, y, ans{N};
    this->NTT(N, 1, x), rhs.NTT(N, 1, y);
    For(i, 0, N - 1) ans[i] = x[i] * y[i];
    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();
}

评测结果