代码

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

using ll = long long;
using ull = unsigned long long;

#define LOG(f...) fprintf(stderr, f)

namespace poly {
  const int N = 1 << 21;
  const int M = 998244353;

  int red(int x) { return x + (M & (x >> 31)); }
  int sub(int x, int y) { return red(x - y); }
  void inc(int &x, int y) { x += y - M; x += M & (x >> 31); }
  int power(int x, int y, int p = 1) {
    for (; y; y >>= 1, x = (ll)x * x % M)
      if (y & 1) p = (ll)p * x % M;
    return p;
  }

  struct FFT {
    int w[N];
    FFT() {
      for (int i = N / 2; i; i >>= 1) {
        w[i] = 1;
        int p = power(3, (M - 1) / 2 / i);
        for (int j = 1; j < i; ++j)
          w[i + j] = (ull)w[i + j - 1] * p % M;
      }
    }

    void DFT(int *a, int n) {
      int *t = a + n;
      for (int k = n / 2, l = n; k; k >>= 1, l >>= 1) {
        int *w = this->w + k, v;
        for (int *i = a; i != t; i += l)
          for (int j = 0; j < k; ++j)
            v = i[j], inc(i[j], i[j + k]), i[j + k] = ull(v - i[j + k] + M) * w[j] % M;
      }
    }
    void IDFT(int *a, int n) {
      int *t = a + n;
      for (int k = 1, l = 2; k < n; k <<= 1, l <<= 1) {
        int *w = this->w + k, v;
        for (int *i = a; i != t; i += l)
          for (int j = 0; j < k; ++j)
            v = (ull)i[j + k] * w[j] % M, i[j + k] = sub(i[j], v), inc(i[j], v);
      }
      reverse(a + 1, a + n);
      for (int i = 0, in = power(n, M - 2); i < n; ++i)
        a[i] = (ull)a[i] * in % M;
    }
  } fft;

  void dot(int *a, const int *b, int n) {
    for (int i = 0; i < n; ++i)
      a[i] = (ll)a[i] * b[i] % M;
  }
  int scale(int n) { return n & (n - 1) ? 2 << __lg(n) : n; }
  void pcopy(const int *src, int *dst, int n) { memcpy(dst, src, sizeof(int) * n); }
  void pclear(int *a, int n) { memset(a, 0, sizeof(int) * n); }
  void scopy(const int *src, int *dst, int n, int len) { n = min(n, len); pcopy(src, dst, n); pclear(dst + n, len - n); }

  static int A[N], B[N];

  void mult(int *f, int lf, int *g, int lg, int *h, int len = -1) {
    if (len == -1) len = scale(lf + lg - 1);
    scopy(f, A, lf, len); scopy(g, B, lg, len); fft.DFT(A, len); fft.DFT(B, len); dot(A, B, len); fft.IDFT(A, len);
    pcopy(A, h, lf + lg - 1);
  }
  void inverse(int *a, int la, int *d, int ld) {
    d[0] = power(a[0], M - 2);
    for (int len = 2; (len >> 1) < ld; len <<= 1) {
      scopy(a, A, la, len); scopy(d, B, len / 2, len);
      fft.DFT(A, len); fft.DFT(B, len); dot(A, B, len); fft.IDFT(A, len); pclear(A, len / 2); A[0] = 0;
      fft.DFT(A, len); dot(A, B, len); fft.IDFT(A, len);
      for (int i = len / 2, li = min(ld, len); i < li; ++i)
        d[i] = red(-A[i]);
    }
  }
}

void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c) {
  poly::mult((int *)a, n + 1, (int *)b, m + 1, (int *)c);
}

评测结果