代码

#include <bits/stdc++.h>

// #define int int64_t

using i64 = int64_t;

const int kMaxN = 4e6 + 5, kMod = 998244353;

int len, polyrev[kMaxN], polyg[kMaxN], polyig[kMaxN];

int qpow(int bs, int idx = kMod - 2) {
  int ret = 1;
  for (; idx; idx >>= 1, bs = (i64)bs * bs % kMod)
    if (idx & 1)
      ret = (i64)ret * bs % kMod;
  return ret;
}

inline int add(int x, int y) {
  return (x + y >= kMod ? x + y - kMod : x + y);
}

inline int sub(int x, int y) {
  return (x >= y ? x - y : x - y + kMod);
}

void prework(int n) {
  int c = 0;
  for (len = 1; len <= n; len <<= 1, ++c) {}
  int gg = qpow(3, (kMod - 1) / len), igg = qpow(gg);
  polyg[0] = polyig[0] = 1;
  for (int i = 1; i < len; ++i) {
    polyg[i] = (i64)polyg[i - 1] * gg % kMod;
    polyig[i] = (i64)polyig[i - 1] * igg % kMod;
    polyrev[i] = (polyrev[i >> 1] >> 1) | ((i & 1) << (c - 1));
    assert(polyrev[i] < len);
  }
}

struct Poly : std::vector<int> {
  using vector::vector;
  using vector::operator [];

  friend Poly operator -(Poly a) {
    static Poly c;
    c.resize(a.size());
    for (int i = 0; i < c.size(); ++i)
      c[i] = sub(0, c[i]);
    return c;
  }
  friend Poly operator +(Poly a, Poly b) {
    static Poly c;
    c.resize(std::max(a.size(), b.size()));
    for (int i = 0; i < c.size(); ++i)
      c[i] = add((i < a.size() ? a[i] : 0), (i < b.size() ? b[i] : 0));
    return c;
  }
  friend Poly operator -(Poly a, Poly b) {
    static Poly c;
    c.resize(std::max(a.size(), b.size()));
    for (int i = 0; i < c.size(); ++i)
      c[i] = sub((i < a.size() ? a[i] : 0), (i < b.size() ? b[i] : 0));
    return c;
  }
  friend void ntt(Poly &a, int len, int *g) {
    if (a.size() < len) a.resize(len);
    for (int i = 0; i < len; ++i)
      if (i < polyrev[i])
        std::swap(a[i], a[polyrev[i]]);
    for (int l = 2; l <= len; l <<= 1) {
      int m = l / 2;
      for (int i = 0; i < len; i += l) {
        for (int j = 0; j < m; ++j) {
          int tmp = (i64)a[i + j + m] * g[len / l * j] % kMod;
          a[i + j + m] = sub(a[i + j], tmp);
          a[i + j] = add(a[i + j], tmp);
        }
      }
    }
  }
  friend Poly operator *(Poly a, Poly b) {
    int n = a.size() + b.size() - 1;
    a.resize(len), b.resize(len);
    ntt(a, len, polyg), ntt(b, len, polyg);
    for (int i = 0; i < len; ++i)
      a[i] = (i64)a[i] * b[i] % kMod;
    ntt(a, len, polyig);
    int invl = qpow(len);
    for (int i = 0; i < len; ++i)
      a[i] = (i64)a[i] * invl % kMod;
    a.resize(n);
    return a;
  }
  friend Poly operator *(Poly a, int b) {
    static Poly c;
    c = a;
    for (auto &x : c) x = (i64)x * b % kMod;
    return c;
  }
  friend Poly operator *(int a, Poly b) {
    static Poly c;
    c = b;
    for (auto &x : c) x = (i64)x * a % kMod;
    return c;
  }
  friend void operator *=(Poly &a, Poly b) {
    int n = a.size() + b.size() - 1;
    ntt(a, len, polyg), ntt(b, len, polyg);
    for (int i = 0; i < len; ++i)
      a[i] = (i64)a[i] * b[i] % kMod;
    ntt(a, len, polyig);
    int invl = qpow(len);
    for (int i = 0; i < len; ++i)
      a[i] = (i64)a[i] * invl % kMod;
    a.resize(n);
  }
  friend Poly Inv(Poly a) {
    Poly G = {qpow(a[0])}, H;
    std::vector<int> vec;
    for (int i = a.size(); i != 1; i = (i + 1) / 2) vec.emplace_back(i);
    vec.emplace_back(1);
    std::reverse(vec.begin(), vec.end());
    for (auto n : vec) {
      prework(n * 2 + 2);
      auto tmp = a;
      tmp.resize(n);
      H = G, G = 2 * H;
      G.resize(n);
      ntt(tmp, len, polyg), ntt(H, len, polyg);
      for (int i = 0; i < len; ++i)
        H[i] = (i64)tmp[i] * H[i] % kMod * H[i] % kMod;
      ntt(H, len, polyig);
      int invl = qpow(len);
      for (int i = 0; i < n; ++i)
        G[i] = sub(G[i], (i64)H[i] * invl % kMod);
    }
    return G;
  }
  friend Poly Ln(Poly a) {
    int n = a.size();
    Poly b, c, tmp;
    if (n == 1) {
      b.resize(a.size());
      return b;
    }
    b.resize(n - 1);
    for (int i = 1; i < n; ++i)
      b[i - 1] = (i64)i * a[i] % kMod;
    tmp = Inv(a);
    prework(2 * n + 2);
    b = b * tmp;
    c.resize(n);
    for (int i = 0; i < n - 1; ++i)
      c[i + 1] = (i64)b[i] * qpow(i + 1) % kMod;
    return c;
  }
};

void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c) {
  Poly aa, bb;
  aa.resize(n + 1), bb.resize(m + 1);
  for (int i = 0; i <= n; ++i) aa[i] = (int)a[i];
  for (int i = 0; i <= m; ++i) bb[i] = (int)b[i];
  prework(n + m + 2);
  aa *= bb;
  for (int i = 0; i <= n + m; ++i) c[i] = (unsigned)aa[i];
}

评测结果