代码

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;
using LL = long long;

const int kM = 998244353, kG = 3;

vector<int> r2;
vector<LL> f, g;

LL Pow(LL b, int e) {
  LL s = 1;
  for (; e; e /= 2, b = b * b % kM) {
    (e & 1) && (s = s * b % kM);
  }
  return s;
}
void NTT(vector<LL> &f) {
  for (int i = 0; i < f.size(); ++i) {
    if (i < r2[i]) {
      swap(f[i], f[r2[i]]);
    }
  }
  for (int l = 1; l < f.size(); l *= 2) {
    LL w1 = Pow(kG, (kM - 1) / l / 2);
    for (int i = 0; i < f.size(); i += l * 2) {
      LL w = 1;
      for (int j = 0; j < l; ++j) {
        LL _f = f[i + l + j] * w % kM;
        f[i + l + j] = (f[i + j] - _f + kM) % kM;
        f[i + j] = (f[i + j] + _f) % kM;
        w = w * w1 % kM;
      }
    }
  }
}

void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c) {
  ++n, ++m;
  f.resize(n), g.resize(m);
  for (int i = 0; i < n; ++i) {
    f[i] = a[i];
  }
  for (int i = 0; i < m; ++i) {
    g[i] = b[i];
  }
  n = (1 << __lg(m += n - 1) + 1);
  r2.resize(n);
  for (int i = 0; i < n; ++i) {
    r2[i] = (r2[i / 2] + (i & 1) * n) / 2;
  }
  f.resize(n), g.resize(n);
  NTT(f), NTT(g);
  for (int i = 0; i < n; ++i) {
    f[i] = f[i] * g[i] % kM;
  }
  NTT(f);
  reverse(f.begin() + 1, f.end());
  LL iv = Pow(n, kM - 2);
  for (LL &i : f) {
    i = i * iv % kM;
  }
  for (int i = 0; i < m; ++i) {
    c[i] = f[i];
  }
}

评测结果