\(QwQ\)

#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define MAXN 4000010

using namespace std;

const double Pi = acos(-1.0);

struct complex {

    double x, y;

    complex (double xx = 0, double yy = 0) {

        x = xx, y = yy;

    }

}a[MAXN], b[MAXN], c[MAXN];

complex operator + (complex a, complex b) {

    return complex(a.x + b.x , a.y + b.y);

}

complex operator - (complex a, complex b) {

    return complex(a.x - b.x , a.y - b.y);

}

complex operator * (complex a, complex b) {

    return complex(a.x * b.x - a.y * b.y , a.x * b.y + a.y * b.x);

}

int N, M, l, limit = 1, r[MAXN];

void fast_fast_tle (complex *A, int type) {

    for (int i = 0; i < limit; i++) {

        if (i < r[i]) {

            swap(A[i], A[r[i]]);

        }

        //effect as A[i] = A_original[r[i]];

    }

    for (int mid = 1; mid < limit; mid <<= 1) {

        complex Wn (cos(Pi / mid) ,type * sin(Pi / mid)); //w (1, mid);

        for (int R = mid << 1, j = 0; j < limit; j += R) {

            //R -> len of sequence

            //j -> last position

            complex w(1, 0); //w (0, mid);

            for (int k = 0; k < mid; k++, w = w * Wn) {

                complex x = A[j + k], y = w * A[j + mid + k];

                A[j + k] = x + y;

                A[j + mid + k] = x - y;

            }

            //mid对应当前的中间值，对应下一次的n。

        }

    }

}

int main () {

    cin >> N >> M;

    for (int i = 0; i <= N; i++) cin >> a[i].x;

    for (int i = 0; i <= M; i++) cin >> b[i].x;

    while (limit <= N + M) limit <<= 1, l++;

    for (int i = l - 1, p = 0; i >= 0; --i) {

        int go_dis = 0;

        while (go_dis < (1 << (l - i - 1))) {

            p = p + 1;

            r[p] = r[p - (1 << (l - i - 1))] + (1 << i);

            ++go_dis;

        }

    }

    fast_fast_tle (a, 1);

    fast_fast_tle (b, 1);

    for (int i = 0; i < limit; i++) {

        c[i] = a[i] * b[i];

    }

    fast_fast_tle(c, -1);

    for (int i = 0; i <= N + M; i++) {

        printf("%d ", (int)(c[i].x / limit + 0.5));

    }

    return 0;

}

附上\(nlogn\)高精乘法的板子

#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#define N 4000010

using namespace std;

struct complex {

    double x, y;

    complex (double xx = 0, double yy = 0) {

        x = xx, y = yy;

    }

}a[N], b[N], c[N];

complex operator + (complex lhs, complex rhs) {

    return complex (lhs.x + rhs.x, lhs.y + rhs.y);

}

complex operator - (complex lhs, complex rhs) {

    return complex (lhs.x - rhs.x, lhs.y - rhs.y);

}

complex operator * (complex lhs, complex rhs) {

    complex t;

    t.x = lhs.x * rhs.x - lhs.y * rhs.y;

    t.y = lhs.x * rhs.y + rhs.x * lhs.y;

    return t;

}

int read () {

    int s = 0, w = 1, ch = getchar ();

    while ('9' < ch || ch < '0') {

        if (ch == '-') w = -1;

        ch = getchar ();

    }

    while ('0' <= ch && ch <= '9') {

        s = s * 10 + ch - '0';

        ch = getchar ();

    }

    return s * w;

}

int r[N];

int n, m, l, lim = 1;

const double pi = acos (-1);

void fast_fast_tle (complex *A, int type) {

    register int i, k, p, len, mid;

    register complex Wn, w, x, y;

    for (i = 0; i < lim; ++i) if (i < r[i]) swap (A[i], A[r[i]]);

    for (mid = 1; mid < lim; mid *= 2) {

        Wn  = complex (cos (pi / mid), type * sin (pi / mid)); // w (1, mid);

        for (len = mid * 2, p = 0; p < lim; p += len) {

            w  = complex (1, 0);

            for (k = 0; k < mid; ++k, w = w * Wn) {// w (k, mid);

                x = A[p + k], y = w * A[p + k + mid];

                A[p + k] = x + y;

                A[p + k + mid] = x - y;

            }

        }

    }

}

int main () {

    n = read (), m = read ();

    register int i, p, go_dis;

    for (i = 0; i <= n; ++i) a[i].x = read ();

    for (i = 0; i <= m; ++i) b[i].x = read ();

    while (lim <= n + m) lim <<= 1, ++l;

    for (i = l - 1, p = 0; i >= 0; --i) {

        go_dis = 0;

        while (go_dis < (1 << (l - i - 1))) {

            p = p + 1;

            r[p] = r[p - (1 << (l - i - 1))] + (1 << i);

            ++go_dis;

        }

    }

    fast_fast_tle (a, +1);

    fast_fast_tle (b, +1);

    for (i = 0; i < lim; ++i) c[i] = a[i] * b[i];

    fast_fast_tle (c, -1);

    for (i = 0; i <= n + m; ++i) printf ("%d ", (int) (c[i].x / lim + 0.5));

}