记录编号	376770	评测结果	AAAAAAWWWW
题目名称	超强的乘法问题	最终得分	60
用户昵称	YGOI_真神名曰驴蛋蛋	是否通过	未通过
代码语言	C++	运行时间	0.140 s
提交时间	2017-02-28 08:07:12	内存使用	8.89 MiB

#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
struct Complex {
	double x,y;
	explicit
		Complex (double xx=0.0,double yy=0.0)
			:x(xx),y(yy){}
	Complex operator + (const Complex&z)
	const {return Complex(x+z.x,y+z.y);}
	Complex operator - (const Complex&z)
	const {return Complex(x-z.x,y-z.y);}
	Complex operator * (const Complex&z)
	const {return Complex(x*z.x-y*z.y,x*z.y+y*z.x);}
	Complex operator * (const double&c)
	const {return Complex(x*c,y*c);}
	void print(const char&c='\n') const {
		printf("%15.9lf (+) %15.9lf[i]%c",x,y,c);
	}
};
typedef long long TYPE;
typedef std::vector<Complex> Vcom;
typedef std::vector<TYPE> Vtype;
const double PI=acos(-1.0);
const int Nbase =5;
const TYPE base =pow(10,Nbase);
const int MAXLENGTH =3E6+10;
char s1[MAXLENGTH],s2[MAXLENGTH];
void rotate(Complex*c,int N) {
	for(int i=1,j=0;i<N;++i) {
		int k=N;
		do{k>>=1;j^=k;}while(j<k);
		if(i<j)std::swap(c[i],c[j]);
	}
}
void fft(Complex*a,int N,const double&is=1.0) {
	rotate(a,N);
	const double pi=is*PI;
	if(N>1){
		for(int i=0;i<N;i+=2) {
			Complex temp=a[i];
			a[i]   = temp + a[i+1];
			a[i+1] = temp - a[i+1];	
		}
	}
	if(N>2){
		const double alpha=pi/2;
		Complex wn(cos(alpha),sin(alpha)),ww=wn*wn;
		Complex u0,u1,v0,v1;
		Complex w0=Complex(1,0),w1=w0*wn;
		//printf("M:=%d %lf\n",4,alpha);wn.print();
		for(int r=0;r<N;r+=4) {
			u0=a[r];
			u1=a[r+1];

			v0=a[r+2]*w0;
			v1=a[r+3]*w1;

			a[r  ]=u0+v0;
			a[r+1]=u1+v1;
			
			a[r+2]=u0-v0;
			a[r+3]=u1-v1;

			//w0.print();
			//w1.print();                             
		}
	}
	if(N>4){
		Complex wn,ww;
		Complex u0,u1,u2,u3;
		Complex v0,v1,v2,v3;
		Complex w0,w1,w2,w3;
		Complex*b0,*b1,*b2,*b3;
		Complex*c0,*c1,*c2,*c3;
		for(int m=8;m<=N;m<<=1) {
			const int mh = m>>1;
			const double alpha=pi/mh;
			wn=Complex(cos(alpha),sin(alpha));
			ww=wn*wn*wn*wn;
			//printf("M:=%d %lf\n",m,alpha);wn.print();
			for(int r=0;r<N;r+=m) {
				w0=Complex(1.0,0.0);
				b0=a+r;
				c0=a+r+mh;

				w1=w0*wn;
				b1=b0+1;
				c1=c0+1;

				w2=w1*wn;
				b2=b1+1;
				c2=c1+1;

				w3=w2*wn;
				b3=b2+1;
				c3=c2+1;
				
				for(int k=0;k<mh;k+=4) {
					u0=b0[k];
					u1=b1[k];
					u2=b2[k];
					u3=b3[k];

					v0=c0[k]*w0;
					v1=c1[k]*w1;
					v2=c2[k]*w2;
					v3=c3[k]*w3;

					b0[k]=u0+v0;
					b1[k]=u1+v1;
					b2[k]=u2+v2;
					b3[k]=u3+v3;

					c0[k]=u0-v0;
					c1[k]=u1-v1;
					c2[k]=u2-v2;
					c3[k]=u3-v3;

				//	w0.print();
				//	w1.print();
				//	w2.print();
				//	w3.print();
					w0=w0*ww;
					w1=w1*ww;
					w2=w2*ww;
					w3=w3*ww;
				}
			}
		}
	}//printf("\n");
	if(is<0.0) {
		const double inv=1.0/N;
		for(int i=0; i<N; ++i) {
			a[i]=a[i]*inv;
			//a[i].print();
		}
	}
}
int convert(char *s,Vcom &a) {
	int x=0,y=1,m=Nbase ;
	for(int i=strlen(s)-1;i>=0;--i) {
		x+=(s[i]-'0')*y;y*=10;
		if(0==--m){
			a.push_back(Complex(x,0.0));
			x=0;y=1;
			m=Nbase;
		}
	}
	if(m!=Nbase )
		a.push_back(Complex(x,0.0));
	return a.size();
}
void show(Vtype &v) {
	static char str[MAXLENGTH]="";
	int i,k;
	for(k=int(v.size())-1;k>0 && v[k]==0;--k);
	for(i=0;k>=0;i+=Nbase ) {
		TYPE x=v[k--];
		for(int j=Nbase -1;j>=0;--j) {
			str[i+j]='0'+(x%10);
			x/=10;
		}
	}
		//printf("k:=%d %lld\n",k,v[k]);
	str[i]='\0';
	//puts(str);
	const char *p=str;
	while('0'==*p)++p;
	if('\0'==*p)--p;
	puts(p);
}
inline int lcn(int a,int b) {
	int n=1;
	while(n<a || n<b) n<<=1;
	return n<<1;
}
int main(){
	freopen("bettermul.in","r",stdin);
	freopen("bettermul.out","w",stdout);
	scanf("%s%s",s1,s2);
	Vcom a,b,c;
	int N=lcn(convert(s1,a),convert(s2,b));
	
	a.resize(N);fft(&a[0],N);
	b.resize(N);fft(&b[0],N);
	c.resize(N);
	for(int i=0;i<N;++i)
		c[i]=a[i]*b[i];
	fft(&c[0],N,-1.0);
	if(N<=2){
		printf("%.0lf",c[0].x+5E-5);
		return 0;
	}
	Vtype v(N);TYPE x=0;
	for(int i=0;i<N;++i ) {
	//	printf("%.2lf %.2lf\n",c[i].x,c[i].y);
		x+=c[i].x+0.5;
		v[i]=x%base;
		x/=base;
	}show(v);
	//while(getchar()!=EOF);
}