代码

#pragma GCC optimize("Ofast")
#include <stdio.h>
#include <string.h>
#include <math.h>
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define PI 3.14159265358979323846
template <class T>
inline void swap(T &a, T &b)
{
	T t=a;
	a=b,b=t;
}
namespace IO
{
	const int BUF_SIZE=1<<15;
	char in_buf[BUF_SIZE],out_buf[BUF_SIZE];
	char *p_in_buf=in_buf+BUF_SIZE;
	char *p_out_buf=out_buf;
	inline char get_char()
	{
		if (p_in_buf==in_buf+BUF_SIZE) fread(in_buf,1,BUF_SIZE,stdin),p_in_buf=in_buf;
		return *(p_in_buf++);
	}
	inline void put_char(char x)
	{
		if (p_out_buf==out_buf+BUF_SIZE) fwrite(out_buf,1,BUF_SIZE, stdout),p_out_buf=out_buf;
		*(p_out_buf++)=x;
	}
	inline void flush()
	{
		if (p_out_buf != out_buf) fwrite(out_buf,1,p_out_buf-out_buf,stdout),p_out_buf=out_buf;
	}
}
#define getchar() IO::get_char()
#define putchar(x) IO::put_char(x)
inline int getint()
{
	int x=0;
	char c=getchar();
	while(c<=32) c=getchar();
	while(c>32) x=x*10+(c&15),c=getchar();
	return x;
}
inline int getint(char &c)
{
	int x=0;
	c=getchar();
	while(c<=32) c=getchar();
	while(c>32) x=x*10+(c&15),c=getchar();
	return x;
}
template <class T>
inline void _putint(T x)
{
	return x?_putint(x/10), putchar((x%10)|48),void():void();
}
template <class T>
inline void putint(T x)
{
	return x==0?putchar('0'),void():_putint(x),void();
}
inline void getline(char *s)
{
	char c=getchar();
	while(c=='\n') c=getchar();
	while(c!='\n') *(s++)=c,c=getchar();
	*s=0;
}
// ==== header ====
#define float double
struct Complex
{
	float x,y;
	Complex conj()
	{
		return (Complex){x,-y};
	}
	Complex conj2()
	{
		return (Complex){-x,y};
	}
};
inline Complex operator + (const Complex &a,const Complex &b)
{
	return (Complex){a.x+b.x,a.y+b.y};
}
inline Complex operator - (const Complex &a,const Complex &b)
{
	return (Complex){a.x-b.x,a.y-b.y};
}
inline Complex operator * (const Complex &a,const Complex &b)
{
	return (Complex){a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x};
}
Complex A[(1<<21)|1], B[(1<<21)|1];
int bitrev[1<<11];
void bitrev_init()
{
	for(register int i=0;i<1<<11;i++)
	{
		int t=0;
		for(register int j=0;j<11;j++) t|=((i>>j)&1)<<(10-j);
		bitrev[i]=t;
	}
}
inline int get_bitrev(int x,int len)
{
	return (bitrev[x>>11]|(bitrev[x&((1<<11)-1)]<<11))>>(22-len);
}
void FFT(Complex *a,int lg_n,bool rev)
{
	int n=1<<lg_n;
	for(register int i=lg_n-1;i>=0;i--)
	{
		int S=1<<i;
		Complex w1=(Complex){cos(PI/S),-sin(PI/S)*(rev?-1:1)};
		for(register int j=0;j<n;j+=S<<1)
		{
			Complex w=(Complex){1.0,0.0};
			Complex *A=a+j;
			for(register int k=0;k<S;k++)
			{
				Complex t=A[k+S];
				A[k+S]=(A[k]-t)*w,A[k]=A[k]+t,w=w*w1;
			}
		}
	}
	for(register int i=0;i<n;i++)
	{
		int t=get_bitrev(i,lg_n);
		if(i<t)
		{
			Complex tmp=a[i];
			a[i]=a[t],a[t]=tmp;
		}
	}
}
void FFT(Complex *a,Complex *b,int lg_n,bool rev)
{
	int n=1<<lg_n;
	for(register int i=lg_n-1;i>=0;i--)
	{
		int S=1<<i;
		Complex w1=(Complex){cos(PI/S),-sin(PI/S)*(rev?-1:1)};
		for(register int j=0;j<n;j+=S<<1)
		{
			Complex w=(Complex){1.0,0.0};
			Complex *A=a+j,*B=b+j;
			for(register int k=0;k<S;k++)
			{
				Complex ta=A[k+S],tb=B[k+S];
				A[k+S]=(A[k]-ta)*w,B[k+S]=(B[k]-tb)*w,A[k]=A[k]+ta,B[k]=B[k]+tb,w=w*w1;
			}
		}
	}
	for(register int i=0;i<n;i++)
	{
		int t=get_bitrev(i,lg_n);
		if(i<t)
		{
			Complex tmp=a[i];
			a[i]=a[t],a[t]=tmp,tmp=b[i],b[i]=b[t],b[t]=tmp;
		}
	}
}
char in_s[(1<<20)|10];
int main()
{
	int n,m;
	n=m=999999;
	int lg_n=3;
	while(1<<lg_n<n+1||1<<lg_n<m+1) ++lg_n;
	bitrev_init();
	int N=1<<lg_n;
	int N2=N>>1;
	getline(in_s);
	for(register int i=0;i<=n;i++)
	{
		// *0.5 is to avoid *2 in later caclulation
		(i&1?A[i>>1].y:A[i>>1].x)=(in_s[n-i]-48)*0.5;
	}
	getline(in_s);
	for(register int i=0;i<=m;i++)
	{
		(i&1?B[i>>1].y:B[i>>1].x)=(in_s[m-i]-48)*0.5;
	}
	FFT(A,B,lg_n,false),A[N]=A[0],B[N]=B[0];
	const Complex w=(Complex){cos(2*PI/N),sin(2*PI/N)};
	Complex w_product=(Complex){1,0};
	for(register int i=0;i<=N2;i++)
	{
		Complex a1=A[i]+A[N-i],a2=A[i]-A[N-i],b1=B[i]+B[N-i],b2=B[i]-B[N-i];
		Complex a=(Complex){a1.x,a2.y},b=(Complex){a2.x,a1.y},c=(Complex){b1.x,b2.y},d=(Complex){b2.x,b1.y};
		// a * c - b * d * delta(x - 1) + a * d + b * c
		// @Signal Processing
		A[i]=a*c+a*d+b*c-b*d*w_product.conj(),A[N - i]=(a*c).conj()+a.conj()*d.conj2()+b.conj2()*c.conj()-b.conj2()*d.conj2()*w_product,w_product=w_product*w;
	}
	FFT(A,lg_n,true);
	float inv_n=1.0/N;
	int ans[2000005];
	for(register int i=0;i<=n+m;i++)
	{
		ans[i]=(int)((i&1?A[i>>1].y:A[i>>1].x)*inv_n+0.5);
	}
	ans[n+m+1]=0;
	for(int i=0;i<=n+m;i++) ans[i+1]+=ans[i]/10,ans[i]=ans[i]%10;
	int i=n+m+1;
	while(!ans[i]) i--;
	while(i>=0) putchar(ans[i]|48),i--;
	IO::flush();
}

评测结果