代码

#include <complex>
#include <algorithm>
using namespace std;

const int N = 1 << 21;

using cp = complex<double>;
const double pi = acos(-1);
 
cp root[N];
 
cp MUL(const cp &a, const cp &b) {
  double x = a.real(), y = a.imag(), u = b.real(), v = b.imag();
  return cp(x * u - y * v, x * v + y * u);
}
 
void init_roots() {
  for (int i = N / 2; i; i >>= 1) {
    double theta = pi / i;
    for (int j = 0; j < i; ++j)
      root[i + j] = polar(1.0, j * theta);
  }
}
void DIF(cp *a, int n) {
  for (int l = n, k = l / 2; k; l >>= 1, k >>= 1) {
    cp *w = root + k;
    for (cp *i = a, *t = a + n; i != t; i += l)
      for (int j = 0; j < k; ++j) {
        cp t = i[j];
        i[j] += i[j + k];
        i[j + k] = (t - i[j + k]) * w[j];
      }
  }
}
void DIT(cp *a, int n) {
  for (int l = 2, k = 1; k < n; l <<= 1, k <<= 1) {
    cp *w = root + k;
    for (cp *i = a, *t = a + n; i != t; i += l)
      for (int j = 0; j < k; ++j) {
        cp t = i[j + k] * w[j];
        i[j + k] = i[j] - t;
        i[j] += t;
      }
  }
  double iv = 1.0 / n;
  reverse(a + 1, a + n);
  for (int i = 0; i < n; ++i)
    a[i] *= iv;
}

cp A[N], B[N];

void poly_multiply(unsigned *a, int n, unsigned *b, int m, unsigned *c) {
  init_roots();
  for (int i = 0; i <= n; ++i)
    A[i].real(a[i]);
  for (int i = 0; i <= m; ++i)
    B[i].real(b[i]);
  DIF(A, N); DIF(B, N);
  for (int i = 0; i < N; ++i)
    A[i] = A[i] * B[i];
  DIT(A, N);
  for (int i = 0; i <= n + m; ++i)
    c[i] = lround(A[i].real());
}

评测结果