代码

#include<bits/stdc++.h>
using namespace std;
#define fo(v,a,b) for(int v = a; v <= b; v++)
#define fr(v,a,b) for(int v = a; v >= b; v--)
#define cl(a,v) memset(a, v, sizeof(a))

const int N = 3000000;

typedef double db;
typedef complex<db> cp;

inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    return x*f;
}

int n, L, len1, len2;

void FFT(cp *a, cp *omg) {
    fo(i,0,n-1) {
        int t = 0;
        fo(j,0,L-1) if(i >> j & 1) t |= (1 << (L - 1 - j));
        if(t > i) swap(a[i], a[t]);
    }
    for(int l = 2; l <= n; l <<= 1) {
        int m = l / 2;
        for(cp *p = a; p != a + n; p += l)
            fo(i,0,m-1) {
                cp t = p[i + m] * omg[n / l * i];
                p[i + m] = p[i] - t, p[i] += t;
            }
    }
}

cp a[N], b[N], c[N], omg[N], inv[N];

void poly_multiply(unsigned *v1, int len1, unsigned *v2, int len2, unsigned *v3)
{
    // freopen("P3803_5.in", "r", stdin);

    fo(i,0,len1) a[i].real(v1[i]);
    fo(i,0,len2) b[i].real(v2[i]);
    
    n = 1; while(n <= len1 + len2) n <<= 1, L++;
    fo(i,0,n-1) {
        omg[i] = cp(cos(2.0 * M_PI * i / n), sin(2.0 * M_PI * i / n));
        inv[i] = conj(omg[i]);
    }

    FFT(a, omg), FFT(b, omg);
    fo(i,0,n-1) c[i] = a[i] * b[i];
    FFT(c, inv);
    fo(i,0,len1 + len2) v3[i] = (unsigned) floor(c[i].real() / n + 0.5);
}

评测结果