代码

#include<cstdio>
#include<cctype>

#ifdef __GNUG__
	#pragma GCC optimize("O3")
	#pragma GCC target("avx2","fma","sse3")
	#pragma omp simd
	#pragma GCC optimize("inline","fast-math","unroll-loops","no-stack-protector")
	#pragma GCC diagnostic error "-fwhole-program"
	#pragma GCC diagnostic error "-fcse-skip-blocks"
	#pragma GCC diagnostic error "-funsafe-loop-optimizations"
#endif

#ifndef  _WIN32
	#define getchar getchar_unlocked
	#define putchar putchar_unlocked
#endif

const int _siz_lt=5e5+5;
const int inf=0x3f3f3f3f;

template<typename _t>
class complex
{
public:
	_t r;
	_t i;
};

template<typename _t>
complex<_t> operator+(complex<_t>_x,complex<_t>_y)
{
	return (complex<_t>){_x.r+_y.r,_x.i+_y.i};
}

template<typename _t>
complex<_t> operator-(complex<_t>_x,complex<_t>_y)
{
	return (complex<_t>){_x.r-_y.r,_x.i-_y.i};
}

template<typename _t>
complex<_t> operator*(complex<_t>_x,complex<_t>_y)
{
	return (complex<_t>){_x.r*_y.r-_x.i*_y.i,_x.r*_y.i+_x.i*_y.r};
}

template<typename _t>
inline
int _digit_str(complex<_t> _str[])
{
	char bit=getchar();
	int _cnt=0;
	while(!isdigit(bit))
		bit=getchar();
	_str[0].r=bit-'0';
	while(isdigit(bit))
	{
		bit=getchar();
		_str[++_cnt].r=bit-'0';
		_str[_cnt].i=0.0;
	}
	_str[_cnt]=(complex<_t>){0.0,0.0};
	return _cnt;
}

complex<double>*_x=new complex<double>[_siz_lt];
complex<double>*_y=new complex<double>[_siz_lt];
complex<double>*_z=new complex<double>[_siz_lt];
static int rev[_siz_lt]={};
static size_t len_x=0,len_y=0,len_z=0;

#include<algorithm>
#include<cmath>

template<typename _t>
void dft(complex<_t>_o[],int y)
{
	complex<_t>*_p=new complex<_t>[_siz_lt];
	for(int i=0;i<len_z;i++)
		_p[i]=_o[rev[i]];
	for(int i=0;i<len_z;i++)
		_o[i]=_p[i];
	for(int i=2;i<=len_z;i<<=1)
	{
		complex<_t> wi=(complex<_t>){(_t)cos(2.0*M_PI/i),(_t)y*sin(2.0*M_PI/i)};
		for(int k=0;k<len_z;k+=i)
		{
			complex<_t> w=(complex<_t>){1.0,0.0};
			complex<_t> _a,_b;
			for(int j=0;j<i/2;j++)
			{
				_a=_o[k+j];
				_b=w*_o[k+j+i/2];
				_o[k+j]=_a+_b;
				_o[k+j+i/2]=_a-_b;
				w=w*wi;
			}
		}
	}
	if(y==-1)
		for(int i=0;i<len_z;i++)
			_o[i].r/=len_z;
	delete[] _p;
	return;
}

template<typename _t>
void fft(complex<_t>_x[],complex<_t>_y[],complex<_t>_z[])
{
	dft(_x,1);
	dft(_y,1);
	for(int i=0;i<len_z;i++)
		_z[i]=_x[i]*_y[i];
	dft(_z,-1);
	delete[] _x;
	delete[] _y;
	return;
}

void prev(int t)
{
	int n=0;
	for(n=0,len_z=1;len_z<t;len_z<<=1)
		n++;
	n++;
	len_z<<=1;
	for(int i=0;i<len_z;i++)
		for(int k=i,j=0;j<n;j++)
		{
			rev[i]<<=1;
			rev[i]|=k&1;
			k>>=1;
		}
	return;
}

#include<algorithm>
void solve_fft(void)
{
	std::reverse(_x,_x+len_x);
	std::reverse(_y,_y+len_y);
	prev(std::max(len_x,len_y));
	fft(_x,_y,_z);
	return;
}

int ans[_siz_lt]={};
void output(void)
{
	for(int i=0;i<len_z;i++)
		ans[i]=(int)(_z[i].r+0.5);
	for(int i=0;i<len_z;i++)
	{
		ans[i+1]+=ans[i]/10;
		ans[i]%=10;
	}
	len_z=len_x+len_y;
	while(!ans[len_z]&&len_z>0)
		len_z--;
	for(int i=len_z;i>=0;i--)
		putchar(ans[i]+'0');
	putchar('\n');
	delete[] _z;
	return;
}

void work(void)
{
	len_x=_digit_str(_x);
	len_y=_digit_str(_y);
	solve_fft();
	output();
	return;
}

int main(int argc,char *argv[],char *env[])
{
	work();
	return 0;
}

评测结果