记录编号	484777	评测结果	AAAAAAAAAAAA
题目名称	增强的乘法问题	最终得分	100
用户昵称	泪寒之雪	是否通过	通过
代码语言	C++	运行时间	0.049 s
提交时间	2018-01-26 20:19:10	内存使用	5.15 MiB

#include<bits/stdc++.h>
#define db double
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define pi acos(-1)
#define N 308123
#define com rrsb
using namespace std;
struct com{
	db r,i;
	com(){}
	com(db a,db b):r(a),i(b){}
};
inline com operator + (const com A,const com B) {
		return com(A.r+B.r,A.i+B.i);
	}
inline com operator - (const com A,const com B) {
		return com(A.r-B.r,A.i-B.i);
	}
inline com operator * (const com A,const com B) {
		return com(A.r*B.r-A.i*B.i,A.i*B.r+A.r*B.i);
	}
com a[N],b[N],X,Y;
int c[N],R[N],n,m,L;
char ch[N];
bool bo;
inline void fft(com *a,int x){
	fo(i,0,n-1) if(i < R[i]) swap(a[i],a[R[i]]);
	for (int i=1;i<n;i<<=1)// 注意这里的n不是输入的n
	 { com wn(cos(pi/i),x*sin(pi/i));
	  for (int j=0;j<n;j+=(i<<1)){
	  	com w(1,0);
	  	 for (int k=0;k<i;k++,w=w*wn) {
	  	 	X=a[j+k]; Y=w*a[j+k+i];
	  	 	a[j+k]=X+Y; a[i+j+k]=X-Y;
		   }
	  }
	}
	if (x==-1) fo(i,0,n-1) a[i].r=a[i].r/n;
}
int main () {
	freopen("mul.in","r",stdin);
	freopen("mul.out","w",stdout);
	//scanf("%d\n",&n); m=n<<1; n--;
	scanf("%s",ch); n=strlen(ch)-1;fo(i,0,n) a[i].r=ch[n-i]-48;m+=n;
	scanf("%s",ch); n=strlen(ch)-1;fo(i,0,n) b[i].r=ch[n-i]-48;m+=n;
	for(n = 1;n <= m ;n <<= 1) ++L;// get size 
    fo(i,0,n-1) R[i] = (R[i>>1]>>1)|((i&1)<<(L-1));//do ni pair
	fft(a,1); fft(b,1);
	fo(i,0,n) a[i]=a[i]*b[i];
	fft(a,-1);
	fo(i,0,m) c[i]=(int)(a[i].r+0.1);
	fo(i,0,m) {
		if (c[i]<10) continue;
		c[i+1]+=c[i]/10; c[i]%=10;
		if (i==m) m++;
	}
	while (m) if (c[m]) break; else m--;
	while (~m) {
	 /*putchar(c[m--]-48);*/
	 printf("%d",c[m--]);bo=true;}
	if (!bo) putchar(48);
	return 0;
}