代码

// Can we go down 100ms?

#include <algorithm>
#include <stdio.h>
#include <math.h>
using namespace std;

typedef double flo;
typedef unsigned long long ll;
typedef unsigned int uint;
const flo pi = 3.1415926535897932384626433832795;
const int N = 1<<21;
struct vec {
    flo x, y;
    vec(){}
    vec(flo x, flo y=0): x(x), y(y) {}
};
inline vec operator+(vec a, vec b) {return vec(a.x+b.x, a.y+b.y);}
inline vec operator-(vec a, vec b) {return vec(a.x-b.x, a.y-b.y);}
inline vec operator*(vec a, vec b) {return vec(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);}
inline vec operator*(vec a, double b) {return vec(a.x*b,a.y*b);}
inline vec operator/(vec a, vec b) {return vec(a.x*b.x+a.y*b.y,a.y*b.x-a.x*b.y);}

vec w[N*2];
void initw(uint n){
	w[1]=vec(1,0);
	for(int i=2;i<n;i<<=1){
		flo t=pi/i;
		vec u(cos(t),sin(t));
		for(int j=0;j<i/2;j++)
			w[i+j*2+1]=(w[i+j*2]=w[i/2+j])*u;
	} {
	    int i = 2*n;
		flo t=pi/i;
		vec u(cos(t),sin(t));
		vec v=u*u, x=u*v;
		for(int j=0;j<i/4;++j) {
            w[i+4*j]=w[i/4+j];
            w[i+4*j+1]=w[i/4+j]*u;
            w[i+4*j+2]=w[i/4+j]*v;
            w[i+4*j+3]=w[i/4+j]*x;
		}
	}
}
vec*getw(uint n){
	return w+n/2;
}

void fft(vec* a, uint n) {
    for (uint i=n; i>>=1; ) {
		vec*w=getw(i<<1);
        for (uint j=0; j<n; j+=i<<1) {
            vec* b=a+j, *c=b+i;
            for (uint k=0; k<i; ++k) {
                vec s=b[k], t=c[k];
                b[k] = s+t; c[k] = (s-t)/w[k];
            }
        }
    }
}
void ifft(vec* a, uint n) {
    for (uint i=1; i<n; i<<=1) {
		vec*w=getw(i<<1);
        for (uint j=0; j<n; j+=i<<1) {
            vec* b=a+j, *c=b+i;
            for (uint k=0; k<i; ++k) {
                vec s=b[k], t=c[k]*w[k];
                b[k] = s+t; c[k] = s-t;
            }
        }
    }
}

void poly_multiply(unsigned *qqa, int n, unsigned *qqb, int m, unsigned *qqc) {
	int n2=(n+1)/2,m2=m/2,u=m-m/2;
	static ll a[N],b[N],c[N];const int L=90000000;
	for(int i=0;i<=n2;++i)
		a[i]=qqa[i*2+1]*L|qqa[i*2];
	for(int i=n2+1;i<=n;++i)
		a[i]=0;
	for(int i=0;i<=u;++i)
		c[i]=qqb[i*2+1];
	for(int i=0;i<=m2;++i)
		b[i]=qqb[i*2];
	int l=1<<__lg(n2+u+1);

	static vec sa[N/2],sb[N/2],sc[N/2],sd[N/2],se[N/2];
	initw(l);
	for(int i=0;i<l;++i){
		sa[i]=vec(a[i],a[i+l])*w[l*2+i];
		sb[i]=vec(b[i],b[i+l])*w[l*2+i];
		sc[i]=vec(c[i],c[i+l])*w[l*2+i];
	}
	fft(sa,l); fft(sb,l); fft(sc,l);
	double lym1 = 1.0/l;
	for(int i=0; i<l; ++i) {
        vec t = sa[i] * lym1;
        sb[i] = sb[i] * t;
        sc[i] = sc[i] * t;
	}
	ifft(sb,l); ifft(sc,l);
	for(int i=0;i<l;++i) {
        vec cc=sc[i]/w[l*2+i], bb=sb[i]/w[l*2+i];
		a[i]=bb.x+.5,a[i+l]=bb.y+.5,
		b[i]=cc.x+.5,b[i+l]=cc.y+.5;
	}
	u=(n+m-1)/2;
	for(int i=0;i<=u;++i)
	{
		b[i]+=a[i]/L;
		*qqc++=(a[i]%L);
		a[i+1]+=b[i]/L;
		*qqc++=(b[i]%L);
	}
	if(!(n+m&1))*qqc++=(a[u+1]&0x7fffff);

}

评测结果