代码

/*+lmake
 * DEFINE += MDEBUG
 * STD = c++11
 */
#include <algorithm>
#include <math.h>
using namespace std;
#ifdef MDEBUG
#define debug(args...)                                                                             \
    {                                                                                              \
        dbg, args;                                                                                 \
        cerr << endl;                                                                              \
    }
#define massert(x) assert(x)
#else
#define debug(args...) // Just strip off all debug tokens
#define massert(x)
#endif
typedef long long LL;
typedef unsigned long long ULL;

#define MAXN 4000000
template <typename Double>
struct Complex
{
    Double r, i;
    Complex(Double r = 0, Double i = 0)
        : r(r)
        , i(i)
    {
    }
    inline Double real() { return r; }
    inline Double imag() { return i; }
};
using complex_t = Complex<double>;
complex_t operator+(const complex_t &a, const complex_t &b)
{
    return { a.r + b.r, a.i + b.i };
}
complex_t operator-(const complex_t &a, const complex_t &b)
{
    return { a.r - b.r, a.i - b.i };
}
complex_t operator*(const complex_t &a, const complex_t &b)
{
    return { a.r * b.r - a.i * b.i, a.r * b.i + a.i * b.r };
}
complex_t a[MAXN + 10];
int rev[MAXN + 10];
const double pi = acos(-1);
void fft(int n, complex_t *a, int flag)
{
    rev[0] = 0;
    for (int i = 1; i < n; ++i)
        rev[i] = rev[i / 2] / 2 + (i % 2) * (n / 2);
    for (int i = 0; i < n; ++i)
        if (i < rev[i])
            swap(a[i], a[rev[i]]);
    for (int i = 1; i < n; i *= 2) {
        int nn = i * 2;
        complex_t wn = (complex_t){ cos(2 * pi / nn), flag * sin(2 * pi / nn) };
        for (int j = 0; j < n; j += nn) {
            complex_t *a1 = a + j, *a2 = a1 + i;
            complex_t w = (complex_t){ 1, 0 };
            for (int k = 0; k < i; ++k) {
                complex_t x = a1[k], y = w * a2[k];
                a1[k] = x + y;
                a2[k] = x - y;
                w = w * wn;
            }
        }
    }
}
void poly_multiply(unsigned *aa, int n, unsigned *bb, int m, unsigned *c)
{
	for(int i=0; i<=n; ++i) a[i].r=aa[i];
	for(int i=0; i<=m; ++i) a[i].i=bb[i];
    LL l = 1;
    for (; l <= n + m; l *= 2)
        ;
    fft(l, a, 1);
    for (int i = 0; i <= l; ++i) {
        a[i] = a[i] * a[i];
    }
    fft(l, a, -1);
	for(int i=0; i<=n+m; ++i) {
		c[i]=unsigned((a[i].i/(2*l))+0.5);
	}
}

评测结果