代码

// 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 = 131072;
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;
            }
        }
    }
}

struct buf{
	char a[1<<25],*s,*t;
	buf():s(a),t(a){
		a[fread(a,1,sizeof a,stdin)]=0;
	}
	~buf(){fwrite(a,1,t-a,stdout);}
	operator uint(){
		int x=0;
		while(*s>47)
			x=x*10+*s++-48; ++s;
		return x;
	}
	void out(uint n){
	    #define pyo(x) *t++=x
	switch(n) {
    case 1000000000 ... 2147483647:
        pyo(48+n/1000000000); n%=1000000000;
    case 100000000 ... 999999999:
        pyo(48+n/100000000); n%=100000000;
    case 10000000 ... 99999999:
        pyo(48+n/10000000); n%=10000000;
    case 1000000 ... 9999999:
        pyo(48+n/1000000); n%=1000000;
    case 100000 ... 999999:
        pyo(48+n/100000); n%=100000;
    case 10000 ... 99999:
        pyo(48+n/10000); n%=10000;
    case 1000 ... 9999:
        pyo(48+n/1000); n%=1000;
    case 100 ... 999:
        pyo(48+n/100); n%=100;
    case 10 ... 99:
        pyo(48+n/10); n%=10;
	}
	pyo(48+n);
	pyo(32);
	}
}it;

int main() {
	static ll a[N],b[N],c[N];
	int n=it,m=it,n2=(n+1)/2,m2=m/2,u=m-m/2;
	const int L=23;
	for(int i=0;i<=n;++i)
		a[i]=it;
	for(int i=0;i<=n2;++i)
		a[i]=a[i*2+1]<<L|a[i*2];
	for(int i=n2+1;i<=n;++i)
		a[i]=0;
	for(int i=0;i<=m;++i)
		b[i]=it;
	for(int i=0;i<=u;++i)
		c[i]=b[i*2+1];
	for(int i=0;i<=m2;++i)
		b[i]=b[i*2];
	for(int i=m2+1;i<=m;++i)
		b[i]=0;
	if(n==0&&m==0)return it.out(a[0]*b[0]),0;
	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]>>23;
		it.out(a[i]&0x7fffff);
		a[i+1]+=b[i]>>23;
		it.out(b[i]&0x7fffff);
	}
	if(!(n+m&1))it.out(a[u+1]&0x7fffff);

}

评测结果