代码

#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<mint> w;
void Init(int n) {
  if (w.size() == n) {
    return;
  }
  w.resize(n);
  w[0] = 1, w[n / 2] = pow(3, (mint::kM - 1) / (n * 2));
  for (int i = n / 2; i > 1; i /= 2) {
    w[i / 2] = w[i] * w[i];
  }
  for (int i = 1; i < n; ++i) {
    w[i] = w[i & i - 1] * w[i & -i];
  }
}
void DIF(Poly &f) {
  int n = f.size();
  Init(n);
  for (int l = n / 2; l >= 1; l /= 2) {
    for (auto p = w.begin(), g = f.begin(); g < f.end(); g += l * 2, ++p) {
      for (auto _g = g; _g < g + l; ++_g) {
        mint f0 = *_g, f1 = *p * _g[l];
        *_g += f1;
        _g[l] = f0 - f1;
      }
    }
  }
}
void DIT(Poly &f) {
  int n = f.size();
  Init(n);
  for (int l = 1; l < n; l *= 2) {
    for (auto p = w.begin(), g = f.begin(); g < f.end(); g += l * 2, ++p) {
      for (auto _g = g; _g < g + l; ++_g) {
        mint f0 = *_g, f1 = _g[l];
        *_g += f1;
        _g[l] = *p * (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);
  DIF(f), DIF(g);
  for (int i = 0; i < n; ++i) {
    f[i] *= g[i];
  }
  DIT(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);
}

评测结果