代码

#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 {
int add(int a, int b) { return (a += b) >= Mod ? a -= Mod : a; }
int sub(int a, int b) { return (a -= b) < 0 ? a += Mod : a; }
void inc(int &a, int b) { (a += b) >= Mod ? a -= Mod : a; }
void dec(int &a, int b) { (a -= b) < 0 ? a += Mod : a; }
int &reduce(int &x) { return x += x >> 31 & Mod; }
void init_Poly();
void DIT(int *A, int lim);
void DIF(int *A, int lim);
Poly mult(const Poly &A, int n, const Poly &B, int m);
ull tmp[N];
int gw[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 DIT(int *A, int lim, bool flag) {
  for (int i = 0; i < lim; ++i)
    tmp[i] = A[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;
      }
    }
  }
  int iv = pow(lim, Mod - 2, Mod);
  for (int i = 0; i < lim; ++i)
    A[i] = tmp[i] % Mod * iv % Mod;
  std::reverse(A + 1, A + lim);
}
void DIF(int *A, int lim, bool flag) {
  for (int i = 0; i < lim; ++i)
    tmp[i] = A[i];
  for (int l = lim / 2; l >= 1; 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] % Mod;
        x[l] = (*x + Mod - o) * *g % Mod, *x += o;
      }
    }
  }
  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);
  DIF(tA, lim, false), DIF(tB, lim, false);
  for (int i = 0; i < lim; ++i)
    tA[i] = 1ll * tA[i] * tB[i] % Mod;
  DIT(tA, lim, true);
  Poly ans(n + m - 1);
  std::copy_n(tA, n + m - 1, ans.begin());
  return ans;
}
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;
}

评测结果