记录编号	144228	评测结果	AAAAAAAAAAAA
题目名称	增强的乘法问题	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	0.026 s
提交时间	2014-12-21 15:18:15	内存使用	22.53 MiB

/****************************************\
* Author : hzoi_ztx
* Title  : cogs 1473. 很强的乘法问题
* ALG    : FFT
* CMT    : 
* Time   : 
\****************************************/

#include <cstdio>
#include <cstring>
#include <cmath>

//using namespace std ;

#define  maxn  530000LL
const double pi = acos(-1.0) ;

struct  COMPLEX {
	double x , y ;
	#define  cpx  COMPLEX
	cpx operator + (const cpx& b) { return (cpx){x+b.x,y+b.y}; }
	cpx operator - (const cpx& b) { return (cpx){x-b.x,y-b.y}; }
	cpx operator * (const cpx& b) { return (cpx){x*b.x-y*b.y,x*b.y+y*b.x}; }
	/*没有白学复变函数论 = = 终于用上了 */
} X[maxn] , Y[maxn] ;

int x[maxn] , y[maxn] , ans[maxn] ;
int len1 , len2 , len ;

template<typename T>inline void Exchange(T&a , T&b) {T c=a;a=b;b=c; }

inline void BRC(cpx* X , int len) {
int i , j , k ;
	for (i=1 , j=len>>1 ; i < len-1 ; i ++ ) {
		if (i < j) Exchange(X[i],X[j]) ;
		k = len>>1 ;
		while (j >= k) { j -= k ; k >>= 1 ; }
		if (j < k) j += k ;
	}
}

inline void DIT_FFT(cpx* X , int len , int sqr) {
cpx O_k , E_k , W , Wn ;
int d , i , k ;
	/* DIT_FFT 求 DFT */
	/* FFT_X[k] = FFT_Odd[k] + (Wn^k) * FFT_Even[k] */
	/* sqr == 1 ：FFT , sqr == -1 : IFFT  */
	BRC(X , len) ; /*进行排序，得到特定的序列便于奇偶划分*/
	for (d = 2 ; d <= len ; d <<= 1 ) {/*从小到大枚举划分长度*/
		Wn = (cpx){cos(sqr*2.0*pi/d),sin(sqr*2.0*pi/d)} ;/* n次单位根 */
		for (i = 0 ; i < len ; i += d) {/* 按划分长度,枚举各个奇偶序列 */
			W = (cpx){1.0,0.0} ; /* Wn^1 */
			for (k = i ; k < i+d/2 ; k ++ ) {
				O_k = X[k] ; /* FFT_E[k] */
				E_k = W*X[k+d/2] ; /* (Wn^k) * FFT_O[k] */
				X[k] = O_k+E_k , X[k+d/2] = O_k-E_k ;/* FFT_X[k] */
				W = W*Wn ;	/* 更新Wn^k */
			}
		}
	}
	if (sqr == -1) {
		/* IFFT 求 IDFT */
   		for(i = 0 ; i < len ; i ++ ) X[i].x /= len ;
   	}
}

inline void FFT_Mul() {
int i ;
	/* 已知两序列x,y及其长度len1,len2,结果存在ans中,并输出 */
	memset(ans , 0 , sizeof (ans)) ; len = 1 ;
	while (len<len1*2 || len<len2*2) len <<= 1 ; 
	for (i = 0 ; i < len1 ; i ++ ) X[i].x = x[len1-i] , X[i].y = 0 ;
	for (i = len1 ; i < len ; i ++ ) X[i].x = X[i].y = 0 ;
	for (i = 0 ; i < len2 ; i ++ ) Y[i].x = y[len2-i] , Y[i].y = 0 ;
	for (i = len2 ; i < len ; i ++ ) Y[i].x = Y[i].y = 0 ;
	DIT_FFT(X , len , 1) ;
	DIT_FFT(Y , len , 1) ;
	for (i = 0 ; i < len ; i ++ ) X[i] = X[i]*Y[i] ;
	DIT_FFT(X , len , -1) ;
	for (i = 0 ; i < len ; i ++ ) ans[i] = (int)(X[i].x+0.5) ;
	for (i = 0 ; i < len ; i ++ ) ans[i+1] += ans[i]/10 , ans[i] %= 10 ;
	len = len1+len2 ;
	while (ans[len]<=0 && len>0) len -- ;
	for (i = len ; i >= 0 ; i -- ) putchar(ans[i]+'0') ;
	putchar('\n') ;
}

char ch ;
int main() {
	/*bettermul  bettermul*/
	#define READ
	#ifdef  READ
		freopen("mul.in" ,"r",stdin ) ;
		freopen("mul.out","w",stdout) ;
	#endif
	while (ch = getchar() , ch < '!') ;
	for (len1 = 0 ; ch > '!' ; ch = getchar() ) {
		x[++len1] = ch-'0' ;
	}
	while (ch = getchar() , ch < '!') ;
	for (len2 = 0 ; ch > '!' ; ch = getchar() ) {
		y[++len2] = ch-'0' ;
	}
	FFT_Mul() ;
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}