代码

#include <bits/stdc++.h>
using namespace std;

#define poly vector<int>

const int mod = 998244353;
const int G = 3;
const int Gi = 332748118;

inline int add(int a, int b) { return a + b >= mod ? a + b - mod : a + b; }
inline int sub(int a, int b) { return a - b < 0 ? a - b + mod : a - b; }
inline int qpow(int a, int b = mod - 2) {
  int res = 1;
  while (b > 0) {
    if (b & 1) res = 1ll * res * a % mod;
    a = 1ll * a * a % mod, b >>= 1;
  }
  return res;
}

namespace Poly {
  poly r, W;
  int lim, L;
  void getR(int n) {
    lim = 1, L = 0;
    while (lim <= n) lim <<= 1, L++;
    r.resize(lim), W.resize(lim);
    for (int i = 0; i < lim; i++) r[i] = (r[i >> 1] >> 1) | ((i & 1) << L - 1);
  }
  void reverse(poly &a) {
    for (int i = 0, j = a.size() - 1; i < j; i++, j--) swap(a[i], a[j]);
  }
  void NTT(poly &a, int opt) {
    for (int i = 0; i < lim; i++) if (i < r[i]) swap(a[i], a[r[i]]);
    for (int mid = 1; mid < lim; mid <<= 1) {
      int Wn = qpow(opt == 1 ? G : Gi, (mod - 1) / (mid << 1));
      W[0] = 1;
      for (int k = 1; k < mid; k++) W[k] = 1ll * W[k - 1] * Wn % mod;
      for (int j = 0; j < lim; j += mid << 1) {
        for (int k = 0; k < mid; k++) {
          int x = a[j + k], y = 1ll * a[j + k + mid] * W[k] % mod;
          a[j + k] = add(x, y);
          a[j + k + mid] = sub(x, y);
        }
      }
    } 
    if (opt == -1) {
      int linv = qpow(lim);
      for (int i = 0; i < lim; i++) a[i] = 1ll * a[i] * linv % mod;
    }
  }
  poly operator * (poly a, poly b) {
    int len = a.size() + b.size() - 1;
    getR(len), a.resize(lim), b.resize(lim);
    NTT(a, 1), NTT(b, 1);
    for (int i = 0; i < lim; i++) a[i] = 1ll * a[i] * b[i] % mod;
    NTT(a, -1), a.resize(len);
    return a;
  }
}
using namespace Poly;
void poly_multiply(unsigned *A, int n, unsigned *B, int m, unsigned *C) {
  vector<int> a(n + 1);
  vector<int> b(m + 1);
  for (int i = 0; i <= n; i++) a[i] = A[i];
  for (int i = 0; i <= m; i++) b[i] = B[i];
  a = a * b;
  for (int i = 0; i <= n + m; i++) C[i] = a[i];
}

评测结果