代码

#include <algorithm>
#include <cassert>
#include <cstdio>
#include <iostream>
#include <vector>

// #define int int64_t

using i64 = int64_t;

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

int polyg[kMaxN];
bool inited;

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); }
inline void inc(int &x, int y) { (x += y) >= kMod ? x -= kMod : x; }
inline void dec(int &x, int y) { (x -= y) < 0 ? x += kMod : x; }

void prework(int n = (kMaxN - 5) / 2) {
  inited = 1;
  int c = 0;
  for (; (1 << c) <= n; ++c) {}
  c = std::min(c - 1, 21);
  polyg[0] = 1, polyg[1 << c] = qpow(31, 1 << 21 - c);
  for (int i = c; i; --i)
    polyg[1 << i - 1] = (i64)polyg[1 << i] * polyg[1 << i] % kMod;
  for (int i = 1; i < (1 << c); ++i) 
    polyg[i] = (i64)polyg[i & (i - 1)] * polyg[i & -i] % kMod;
}

int getlen(int n) {
  int len = 1;
  for (; len <= n; len <<= 1) {}
  return 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 dif(Poly &a, int len) {
    if (a.size() < len) a.resize(len);
    for (int l = len; l != 1; l >>= 1) {
      int m = l / 2;
      for (int i = 0, k = 0; i < len; i += l, ++k) {
        for (int j = 0; j < m; ++j) {
          int tmp = (i64)a[i + j + m] * polyg[k] % kMod;
          a[i + j + m] = sub(a[i + j], tmp);
          inc(a[i + j], tmp);
        }
      }
    }
  }
  friend void dit(Poly &a, int len) {
    if (a.size() < len) a.resize(len);
    for (int l = 2; l <= len; l <<= 1) {
      int m = l / 2;
      for (int i = 0, k = 0; i < len; i += l, ++k) {
        for (int j = 0; j < m; ++j) {
          int tmp = a[i + j + m];
          a[i + j + m] = (i64)sub(a[i + j], tmp) * polyg[k] % kMod;
          inc(a[i + j], tmp);
        }
      }
    }
    int invl = qpow(len);
    for (int i = 0; i < len; ++i)
      a[i] = (i64)a[i] * invl % kMod;
    std::reverse(a.begin() + 1, a.begin() + len);
  }
  friend Poly operator *(Poly a, Poly b) {
    if (!inited) prework();
    int n = a.size() + b.size() - 1, len = getlen(n);
    a.resize(len), b.resize(len);
    dif(a, len), dif(b, len);
    for (int i = 0; i < len; ++i)
      a[i] = (i64)a[i] * b[i] % kMod;
    dit(a, len);
    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) {
    if (!inited) prework();
    int n = a.size() + b.size() - 1, len = getlen(n);
    a.resize(len), b.resize(len);
    dif(a, len), dif(b, len);
    for (int i = 0; i < len; ++i)
      a[i] = (i64)a[i] * b[i] % kMod;
    dit(a, len);
    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) {
      auto tmp = a;
      tmp.resize(n);
      H = G, G = 2 * H;
      G.resize(n);
      int len = getlen(n * 2 + 2);
      if (!inited) prework();
      dif(tmp, len), dif(H, len);
      for (int i = 0; i < len; ++i)
        H[i] = (i64)tmp[i] * H[i] % kMod * H[i] % kMod;
      dit(H, len);
      for (int i = 0; i < n; ++i)
        G[i] = sub(G[i], H[i]);
    }
    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);
    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(n + 1), bb(m + 1);
  for (int i = 0; i <= n; ++i)
    aa[i] = a[i];
  for (int i = 0; i <= m; ++i)
    bb[i] = b[i];
  aa *= bb;
  for (int i = 0; i <= n + m; ++i)
    c[i] = aa[i];
}

评测结果