代码

#include <bits/stdc++.h>

typedef unsigned uint;
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int, int> pii;
const int iinf = 2147483647;
const ll llinf = 9223372036854775807ll;

const int N = 2100000;
const int Mod = 998244353, g = 3;
typedef std::vector<int> Poly;

int pow(int a, int b, int m);

namespace Pol {
void getr(int lim);
void init_Poly();
void NTT(int *A, int lim, bool flag);
Poly mult(const Poly &A, int n, const Poly &B, int m);
ull tmp[N];
int gw[N];
int r[N];
}  // namespace Pol

void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c) {
  Pol::init_Poly();
  ++n, ++m;
  Poly F(n), G(m);
  for (int i = 0; i < n; ++i)
    F[i] = a[i];
  for (int i = 0; i < m; ++i)
    G[i] = b[i];
  Poly ans = Pol::mult(F, n, G, m);
  for (int i = 0; i < n + m - 1; ++i)
    c[i] = ans[i];
}

namespace Pol {
void NTT(int *A, int lim, bool flag) {
  for (int i = 0; i < lim; ++i)
    tmp[i] = A[r[i]];
  for (int l = 1; l < lim; l <<= 1) {
    ull *k = tmp;
    for (int i = 0; i < lim; i += (l << 1), k += (l << 1)) {
      ull *x = k;
      for (int j = 0, *g = gw + l; j < l; ++j, ++x, ++g) {
        ull o = x[l] * *g % Mod;
        x[l] = *x + Mod - o, *x += o;
      }
    }
  }
  if (flag) {
    std::reverse(tmp + 1, tmp + lim);
    int iv = pow(lim, Mod - 2, Mod);
    for (int i = 0; i < lim; ++i)
      tmp[i] = tmp[i] % Mod * iv;
  }
  for (int i = 0; i < lim; ++i)
    A[i] = tmp[i] % Mod;
}
Poly mult(const Poly &A, int n, const Poly &B, int m) {
  int lim = 1;
  while (lim < (n + m - 1))
    lim <<= 1;
  static int tA[N], tB[N];
  std::copy_n(A.begin(), n, tA), std::fill(tA + n, tA + lim, 0);
  std::copy_n(B.begin(), m, tB), std::fill(tB + m, tB + lim, 0);
  getr(lim);
  NTT(tA, lim, false), NTT(tB, lim, false);
  for (int i = 0; i < lim; ++i)
    tA[i] = 1ll * tA[i] * tB[i] % Mod;
  NTT(tA, lim, true);
  Poly ans(n + m - 1);
  std::copy_n(tA, n + m - 1, ans.begin());
  return ans;
}
void getr(int lim) {
  for (int i = 0; i < lim; ++i)
    r[i] = (r[i >> 1] >> 1) | ((i & 1) * (lim >> 1));
}
void init_Poly() {
  for (int l = 1; l < (1 << 21); l <<= 1) {
    gw[l] = 1;
    int gn = pow(g, (Mod - 1) / (l << 1), Mod);
    for (int j = 1; j < l; ++j) {
      gw[l | j] = 1ll * gw[l | (j - 1)] * gn % Mod;
    }
  }
}
}  // namespace Pol

int pow(int a, int b, int m) {
  int ans = 1, now = a;
  while (b) {
    if (b & 1) ans = 1ll * ans * now % m;
    now = 1ll * now * now % m;
    b >>= 1;
  }
  return ans;
}

评测结果