代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int mod = 998244353, o = 21, len = 1 << o;

int power(int a, int n) {
  int tp = 1;
  while (n) {
    if (n & 1)
      tp = 1ll *tp * a % mod;
    a = 1ll * a * a % mod, n >>= 1;
  }
  return tp;
}

typedef unsigned long long u64;
int w[len], r[len], up, l;

void init() {
  const int w0 = power(3, (mod - 1) >> o);
  w[len >> 1] = 1;
  for (int i = (len >> 1) + 1; i != len; i++)
    w[i] = 1ll * w[i - 1] * w0 % mod;
  for (int i = (len >> 1) - 1; i; i--)
    w[i] = w[i << 1];
  for (int i = 0; i != len; i++)
    r[i] = (r[i >> 1] >> 1) | ((i & 1) << (o - 1));
}

void ntt(int *a, int n, bool op) {
  static u64 t[len];
  const int b = 2;
  for (int op = 0; op != b; op++)
    for (int i = op; i < n; i += b)
      t[i] = a[r[i]];
  for (int l = 1; l != n; l <<= 1) {
    int *k = w + l;
    for (u64 *f = t; f != t + n; f += l)
      for (int *j = k; j != k + l; j++, f++) {
        u64 x = *f;
        int y = f[l] * *j % mod;
        f[l] = x + mod - y, *f += y;
      }
  }
  if (op) {
    for (int i = 0, x = mod - (mod >> l); i != n; i++)
      a[i] = t[i] * x % mod;
    reverse(a + 1, a + n);
  } else
    for (int i = 0; i != n; i++)
      a[i] = t[i] % mod;
}

int pre(int n) {
  l = 32 - __builtin_clz(n);
  return up = 1 << l;
}

void poly_multiply(unsigned *f, int n, unsigned *g, int m, unsigned *h) {
  static int x[len], y[len];
  init();
  memcpy(x, f, (n + 1) << 2), memcpy(y, g, (m + 1) << 2);
  pre(n + m), ntt(x, up, 0), ntt(y, up, 0);
  for (int i = 0; i != up; i++)
    x[i] = 1ll * x[i] * y[i] % mod;
  ntt(x, up, 1);
  memcpy(h, x, (n + m + 1) << 2);
}

评测结果