代码

#include<algorithm>

using ll = long long;

constexpr int mod = 998244353, g = 3;

inline int Pow(ll b, ll p, ll m) {
  b %= m; ll s = 1 % m;
  for (; p; p >>= 1, b = b * b % m)
    if (p & 1) s = s * b % m;
  return s;
}

namespace Poly {
  using Poly_t = int[1<<18|1];

  int l;
  Poly_t F, G, w, to;

  void prework(int N) {
    int lim, rt;
    for (lim = 1, l = -1; lim < N << 1; lim <<= 1, ++l);
    for (int i = 0; i < lim; ++i)
      to[i] = (to[i >> 1] >> 1) | ((i & 1) << l);
    ++l;
    rt = Pow(g, (mod - 1) >> l, mod);
    w[lim >> 1] = 1;
    for (int i = (lim >> 1) + 1; i < lim; ++i)
      w[i] = 1ll * w[i - 1] * rt % mod;
    for (int i = (lim >> 1) - 1; i; --i)
      w[i] = w[i << 1];
  }

  void DFT(int N, unsigned *g) {
    static unsigned long long f[1<<18|1];
    int d = l, t;
    for (int lim = 1; lim < N; lim <<= 1, --d);
    for (int i = 0; i < N; ++i)
      f[i] = g[to[i] >> d];

    for (int m = 1; m < N; m <<= 1)
      for (int j = 0; j < N; j += m << 1)
        for (int k = 0; k < m; ++k) {
          t = f[j | k | m] * w[k | m] % mod;
          f[j | k | m] = f[j | k] - t + mod;
          f[j | k] += t;
        }

    for (int i = 0; i < N; ++i)
      g[i] = f[i] % mod;
  }

  void IDFT(int N, unsigned *f) {
    std::reverse(f + 1, f + N);
    DFT(N, f);
    for (int i = 0, k = mod - (mod - 1) / N; i < N; ++i)
      f[i] = 1ll * f[i] * k % mod;
  }
} // Poly
using namespace Poly;

void poly_multiply(unsigned *F, int N, unsigned *G, int M, unsigned *H) {
  int lim;
  prework(std::max(N + 1, M + 1));

  for (lim = 1; lim <= N + M; lim <<= 1);
  DFT(lim, F), DFT(lim, G);
  for (int i = 0; i < lim; ++i)
    H[i] = 1ll * F[i] * G[i] % mod;
  IDFT(lim, H);
}

评测结果