代码

# include <bits/stdc++.h>

using namespace std;

namespace lyre {
  constexpr int P(998'244'353);
  constexpr int pow(int a, int n) {
    auto r(1);
    while (n) {
      r = 1l * r * (n & 1 ? a : 1) % P;
      n >>= 1, a = 1l * a * a % P;
    }
    return r;
  }
  constexpr int inv(int a)
  { return pow(a, P - 2); }
  class poly : public vector<int> {
    public:
    using vector<int>::vector;
    void reserve() {
      while (size() != (size() & -size()))
        emplace_back();
    }
    void dif() {
      int const n(size());
      vector<int> trans(n);
      for (int i(0); i < n; ++i)
        trans[i] = (trans[i >> 1] >> 1) + (i & 1) * (n >> 1);
      for (int i(0); i < n; ++i)
        if (i < trans[i]) std::swap(at(i), at(trans[i]));
      for (int mid(1); mid < n; mid *= 2) {
        auto w1(pow(3, (P - 1) / (mid * 2)));
        for (int i(0); i < n; i += mid * 2) {
          auto wk(1);
          for (int j(0), k(mid); j < mid; ++j, ++k) {
            auto x(at(i + j));
            auto y(1l * wk * at(i + k) % P);
            at(i + j) = (x + y) % P;
            at(i + k) = (x + P - y) % P;
            wk = 1l * wk * w1 % P;
          }
        }
      }
    }
    void dit() {
      int const n(size());
      vector<int> trans(n);
      for (int i(0); i < n; ++i)
        trans[i] = (trans[i >> 1] >> 1) + (i & 1) * (n >> 1);
      for (int i(0); i < n; ++i)
        if (i < trans[i]) std::swap(at(i), at(trans[i]));
      for (int mid(1); mid < n; mid *= 2) {
        auto w1(pow(inv(3), (P - 1) / (mid * 2)));
        for (int i(0); i < n; i += mid * 2) {
          auto wk(1);
          for (int j(0), k(mid); j < mid; ++j, ++k) {
            auto x(at(i + j));
            auto y(1l * wk * at(i + k) % P);
            at(i + j) = (x + y) % P;
            at(i + k) = (x + P - y) % P;
            wk = 1l * wk * w1 % P;
          }
        }
      }
      for (int i(0); i < n; ++i)
        at(i) = 1l * at(i) * inv(n) % P;
    }
    poly operator*(const poly &o) const {
      auto f(*this), g(o);
      poly h(f.size() + g.size() - 1);
      h.reserve();
      f.resize(h.size()), f.dif();
      g.resize(h.size()), g.dif();
      for (auto i(0u); i < h.size(); ++i)
        h[i] = 1l * f[i] * g[i] % P;
      h.dit();
      return h;
    }
  };
  void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c) {
    poly f(n + 1), g(m + 1);
    for (int i(0); i <= n; ++i) f[i] = a[i];
    for (int i(0); i <= m; ++i) g[i] = b[i];
    poly const h(f * g);
    for (int i(0); i <= n + m; ++i) c[i] = h[i];
  }
}

void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c)
{ return lyre::poly_multiply(a, n, b, m, c); }

评测结果