代码

#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
const int fMaxn = maxn << 2; // fMaxn >= 4*maxn (1025 need 4096)
namespace FFT {
    // typedef long double ld;
    const double pi = acos(-1.0);
    struct Complex {
        double r, i;
        Complex(double r = 0, double i = 0):r(r), i(i) {};
        Complex operator + (const Complex & rhs) {
            return Complex(r + rhs.r, i + rhs.i);
        }
        Complex operator - (const Complex & rhs) {
            return Complex(r - rhs.r, i - rhs.i);
        }
        Complex operator * (const Complex &rhs) {
            return Complex(r * rhs.r - i * rhs.i, i * rhs.r + r * rhs.i);
        }
    } va[fMaxn], vb[fMaxn], vc[fMaxn];
    void change(Complex F[], int len) {
        int j = len >> 1;
        for(int i = 1; i < len - 1; ++i) {
            if(i < j) {
                swap(F[i], F[j]);
            }
            int k = len >> 1;
            while(j >= k) {
                j -= k;
                k >>= 1;
            }
            if(j < k) {
                j += k;
            }
        }
    }
    void fft(Complex F[], int len, int t) {
        change(F, len);
        for(int h = 2; h <= len; h <<= 1) {
            Complex wn(cos(-t*2.0*pi/h), sin(-t*2.0*pi/h));
            for(int j = 0; j < len; j += h) {
                Complex E(1, 0);
                for(int k = j; k < j + h/2; ++k) {
                    Complex u = F[k];
                    Complex v = E*F[k + h/2];
                    F[k] = u + v;
                    F[k + h/2] = u - v;
                    E = E*wn;
                }
            }
        }
        if(t == -1) {
            for(int i = 0; i < len; i++) {
                F[i].r /= len;
            }
        }
    }
    template<class T>
    int init(T a[], T b[], int la, int lb) {
        int lc = 1, mi = 2*max(la, lb);
        while(lc < mi) {
            lc <<= 1;
        }
        for(int i = 0; i < la; ++i) {
            va[i] = {(double)a[i], 0.0};
        }
        for(int i = la; i < lc; ++i) {
            va[i] = {0.0, 0.0};
        }
        for(int i = 0; i < lb; ++i) {
            vb[i] = {(double)b[i], 0.0};
        }
        for(int i = lb; i < lc; ++i) {
            vb[i] = {0.0, 0.0};
        }
        return lc;
    }
    template<class T>
    int solve(T a[], T b[], T c[], int la, int lb) { // id: [0, la), [0, lb), [0, lc)
        int lc = init(a, b, la, lb);
        fft(va, lc, 1);
        fft(vb, lc, 1);
        for(int i = 0; i < lc; ++i) {
            vc[i] = va[i]*vb[i];
        }
        fft(vc, lc, -1);
        for(int i = 0; i < la+lb+2; ++i) {
            // c[i] = vc[i].r; // double
            c[i] = (unsigned)round(vc[i].r); // int
            // c[i] = (ll)round(vc[i].r); // ll
        }
        return lc;
    }
}

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

评测结果