代码

#include<bits/stdc++.h>
#define M_PI		3.14159265358979323846
using namespace std;
using ll=long long;
using ld=long double;
using pii=pair<int,int>;
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " = " << x << endl;
using Complex=pair<double,double>;
#define x first
#define y second
inline const Complex	operator *(const Complex &a,const double &d) {
	return {a.x*d,a.y*d};
}
inline const Complex	operator *(const Complex &a,const Complex &b) {
	return {a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};
}
inline const Complex	operator +(const Complex &a,const Complex &b) {
	return {a.x+b.x,a.y+b.y};
}
inline const Complex	operator -(const Complex &a,const Complex &b) {
	return {a.x-b.x,a.y-b.y};
}

using Comp=Complex;
const int MAX_N=1<<21;//33554432
using uint=unsigned int;
void change(Comp *y,uint len){//nlogn
	for(uint i=1,k,j=len>>1;i<len-1;++i){
		if(i<j)swap(y[i],y[j]);
		k=len>>1;
		while(j>=k){
			j=j-k;
			k=k>>1;
		}
		if(j<k)j+=k;
	}
}
void DFT(Comp *f,const uint n){
	change(f,n);
	const double M_PI2=2*M_PI;
	double hd=M_PI2*0.5;
	for(uint h=2;h<=n;h<<=1,hd*=0.5){
		const uint h2=h>>1;
		Comp wn(cos(hd),sin(hd)),w;
		for(uint j=0;j<n;j+=h){
			w.x=1,w.y=0;
			for(uint k=j;k<j+h2;++k){
				Comp u=f[k],t=w*f[k+h2];
				f[k+h2]=u-t;
				f[k]=u+t;
				w=w*wn;
			}
		}
	}
	return ;
} 
void IDFT(Comp *f,const uint n){
	change(f,n);
	const double M_PI2=2*M_PI;
	double hd=M_PI2*0.5;
	for(uint h=2;h<=n;h<<=1,hd*=0.5){
		const uint h2=h>>1;
		Comp wn(cos(hd),sin(-hd)),w;
		for(uint j=0;j<n;j+=h){
			w.x=1,w.y=0;
			for(uint k=j;k<j+h2;++k){
				Comp u=f[k],t=w*f[k+h2];
				f[k]=u+t;
				f[k+h2]=u-t;
				w=w*wn;
			}
		}
	}
	return ;
} 
Comp a[MAX_N],b[MAX_N];
unsigned av[3000000];
unsigned bv[3000000];
void poly_multiply(unsigned *ax, int n, unsigned *bx, int m, unsigned *c)
{
	n++,m++;
	for(uint i=0;i<n;++i){
		a[i].x=ax[i];
	}
	for(uint i=0;i<m;++i){
		b[i].x=bx[i];
	}
	uint len=1;
	while(len<(n*2)||len<(m*2))len*=2;
	DFT(a,len);
	DFT(b,len);
	for(uint i=0;i<len;++i)
	a[i]=a[i]*b[i];
	IDFT(a,len);
	const double ilen=1.0/len; 
	for(uint i=0;i<n+m-1;++i)
	c[i]=int(a[i].x*ilen+0.5);
}

评测结果