代码

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
using uint = unsigned int;
using ull = unsigned long long;

struct mint {
  static const uint kM = 998244353;

  uint v;

  mint() = default;
  static mint safe_mod(uint _v) {
    mint x;
    if ((x.v = _v) >= kM) {
      x.v -= kM;
    }
    return x;
  }
  mint(ull _v) { v = _v % kM; }
  operator uint() { return v; }
  mint operator+(const mint &o) const { return safe_mod(v + o.v); }
  mint &operator+=(const mint &o) { return *this = safe_mod(v + o.v); }
  mint operator-() const {
    mint x;
    x.v = (v ? kM - v : 0);
    return x;
  }
  mint operator-(const mint &o) const { return safe_mod(v + kM - o.v); }
  mint &operator-=(const mint &o) { return *this = safe_mod(v + kM - o.v); }
  mint operator*(const mint &o) const { return mint(1ull * v * o.v); }
  mint &operator*=(const mint &o) { return *this = mint(1ull * v * o.v); }
  static uint inv(uint a, uint m = kM) {
    return a == 1 ? 1 : m - 1ull * inv(m % a, a) * m / a;
  }
  mint operator/(const mint &o) const { return mint(1ull * v * inv(o.v)); }
  mint &operator/=(const mint &o) { return *this = mint(1ull * v * inv(o.v)); }
};
istream &operator>>(istream &in, mint &x) { return in >> x.v; }
ostream &operator<<(ostream &out, const mint &x) { return out << x.v; }
mint pow(mint b, uint e) {
  mint s = 1;
  for (; e; e /= 2, b *= b) {
    if (e & 1) {
      s *= b;
    }
  }
  return s;
}

using Poly = vector<mint>;

namespace multiplier {
vector<vector<mint>> w(1, vector<mint>(1, 1));
void Init(int n) {
  for (int l = w.back().size(); l < n;) {
    l *= 2;
    vector<mint> _w;
    _w.push_back(1);
    mint v = 1, w1 = pow(3, (mint::kM - 1) / l);
    for (int i = 1; i < l; ++i) {
      _w.push_back(v *= w1);
    }
    w.push_back(_w);
  }
}
void DIT(Poly &f) {
  int n = f.size();
  Init(n);
  for (int l = n / 2; l >= 1; l /= 2) {
    for (int i = 0; i < n; i += l * 2) {
      for (int j = 0; j < l; ++j) {
        mint f0 = f[i + j], f1 = f[i + l + j];
        f[i + j] += f1;
        f[i + l + j] = w[__lg(l) + 1][j] * (f0 - f1);
      }
    }
  }
}
void DIF(Poly &f) {
  int n = f.size();
  Init(n);
  for (int l = 1; l < n; l *= 2) {
    for (int i = 0; i < n; i += l * 2) {
      for (int j = 0; j < l; ++j) {
        mint f0 = f[i + j], f1 = w[__lg(l) + 1][j] * f[i + l + j];
        f[i + j] += f1;
        f[i + l + j] = f0 - f1;
      }
    }
  }
  reverse(f.begin() + 1, f.end());
  mint iv = mint::inv(n);
  for (mint &i : f) {
    i *= iv;
  }
}
Poly Conv(Poly f, Poly g) {
  int rn = f.size(), rm = g.size();
  int n = (1 << __lg(rn + rm - 1));
  if (n < rn + rm - 1) {
    n *= 2;
  }
  f.resize(n), g.resize(n);
  DIT(f), DIT(g);
  for (int i = 0; i < n; ++i) {
    f[i] *= g[i];
  }
  DIF(f), f.resize(rn + rm - 1);
  return f;
}
}; // namespace multiplier
using multiplier::Conv;
using multiplier::DIF;
using multiplier::DIT;

void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c) {
  vector<mint> f(a, a + n + 1);
  vector<mint> g(b, b + m + 1);
  vector<mint> h = Conv(f, g);
  copy_n(h.begin(), n + m + 1, c);
}

评测结果