代码

#include <algorithm>
#include <cstdio>
using namespace std;

#define int unsigned

const int LOGN = 22, N = 1 << LOGN;

template<int P>
struct ModInt {
private:
  inline ModInt qpow(int y) const {
    ModInt res = 1, x = v;
    for (; y; y >>= 1, x *= x) if (y & 1) res *= x;
    return res;
  }

public:
  int v;
  ModInt() = default;
  ModInt(int x) : v(x) { }
  static inline constexpr int mod() { return P; }
  inline void read() { scanf("%d", &v); }
  inline ModInt &operator+=(const ModInt &x) { (v += x.v) >= P && (v -= P); return *this; }
  inline ModInt &operator-=(const ModInt &x) { (v += P - x.v) >= P && (v -= P); return *this; }
  inline ModInt &operator*=(const ModInt &x) { v = 1LL * v * x.v % P; return *this; }
  inline ModInt operator-() { return ModInt(P - v); }
  friend inline ModInt operator+(const ModInt &x, const ModInt &y) { return ModInt(x) += y; }
  friend inline ModInt operator-(const ModInt &x, const ModInt &y) { return ModInt(x) -= y; }
  friend inline ModInt operator*(const ModInt &x, const ModInt &y) { return ModInt(x) *= y; }
  inline ModInt pow(int x) const { return qpow(x); }
  inline ModInt pow(const ModInt &x) const { return qpow(x.v); }
  inline ModInt inv() const { return pow(P - 2); }
};

typedef ModInt<998244353> mint, *Poly;

int rev[N + 10];

inline int init(int n) {
  const int lg = __lg(n) + 1, len = 1 << lg;
  for (int i = 0; i < len; i++) rev[i] = (rev[i >> 1] >> 1) | ((i & 1) << (lg - 1));
  return len;
}

template<bool inv = 0>
void ntt(Poly f, const int n) {
  for (int i = 0; i < n; i++) if (i < rev[i]) swap(f[i], f[rev[i]]);
  for (int len = 2; len <= n; len <<= 1) {
    const mint w0 = mint(3).pow((mint().mod() - 1) / len);
    const int mid = len >> 1;
    for (int i = 0; i < n; i += len) {
      mint w = 1;
      for (int j = i; j < i + mid; j++) {
        const mint x = f[j], y = w * f[j + mid];
        f[j] = x + y, f[j + mid] = x - y;
        w *= w0;
      }
    }
  }
  if (inv) {
    reverse(f + 1, f + n);
    const mint iv = mint(n).inv();
    for (int i = 0; i < n; i++) f[i] *= iv;
  }
}

inline void mul(Poly f, Poly g, Poly h, int n, int m) {
  int len = init(n + m);
  ntt(f, len), ntt(g, len);
  for (int i = 0; i < len; i++) h[i] = f[i] * g[i];
  ntt<1>(h, len);
}

mint a[N], b[N];

void poly_multiply(unsigned *a, signed n, unsigned *b, signed m, unsigned *c) {
  n++, m++;
  for (int i = 0; i < n; i++) ::a[i] = a[i];
  for (int i = 0; i < m; i++) ::b[i] = b[i];
  mul(::a, ::b, ::a, n, m);
  for (int i = 0; i < n + m - 1; i++) c[i] = ::a[i].v;
}

评测结果