代码

#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(unsigned *a, int n, bool op) {
  static u64 t[len];
  for (int i = 0; i != n; i += 2) {
    int x = a[r[i] >> (o - l)], y = a[r[i + 1] >> (o - l)];
    t[i] = x + y, t[i + 1] = x + mod - y;
  }
  for (int l = 2; l != n; l <<= 1) {
    if (l == (1 << 18))
      for (u64 *f = t; f != t + n; f++)
        *f %= mod;
    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) {
    if (n == (1 << 18))
      for (u64 *f = t; f != t + n; f++)
        *f %= mod;
    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) {
  init();
  pre(n + m), ntt(f, up, 0), ntt(g, up, 0);
  for (int i = 0; i != up; i++)
    h[i] = 1ll * f[i] * g[i] % mod;
  ntt(h, up, 1);
}

评测结果