记录编号	510064	评测结果	AAAAAAAAAA
题目名称	超强的乘法问题	最终得分	100
用户昵称	Chtholly	是否通过	通过
代码语言	C++	运行时间	0.994 s
提交时间	2018-09-17 21:13:36	内存使用	14.65 MiB

#include<bits/stdc++.h>
#define maxn 800010
#define Base 10
using namespace std;
const double PI= acos(-1.0) , eps = 1e-6;
class Complex{
	public:
		double x,y;
		Complex(double x_=0,double y_=0){
			x=x_;
			y=y_;
		}
};
Complex operator + (Complex a,Complex b){return Complex(a.x+b.x,a.y+b.y);}
Complex operator - (Complex a,Complex b){return Complex(a.x-b.x,a.y-b.y);}
Complex operator * (Complex a,Complex b){return Complex(a.x*b.x-a.y*b.y,a.x*b.y+b.x*a.y);}
Complex operator * (Complex a,double b){return Complex(a.x*b,a.y*b);}
Complex operator / (Complex a,double b){return Complex(a.x/b,a.y/b);}
void swap (Complex &a,Complex &b){Complex c=a;a=b,b=c;}
class Poly{
	public:
		int n;
		//n为项数 
		Complex s[maxn];
		void Init(char str[]){
			//初始化
			n=strlen(str);
			for(int i=0;i<n;i++) s[i]=Complex(str[n-1-i]-'0',0);
		}
		void read(void){
			static char str[maxn];
			//static char 静态变量 
			scanf("%s",str);
			Init(str);
			//读入 后初始化 
		}
		void Assign(char str[]){
			static int a[maxn];
			int len;
			for(int i=0;i<n;i++) a[i]=int(s[i].x+0.5);
			for(len=0;len<n||a[len];len++){
				a[len+1]+=a[len]/Base;
				a[len]%=Base;
			}
			while(len>1&&!a[len-1]) len--;
			for(int i=0;i<len;i++) str[i]=a[len-1-i]+'0';
			str[len]=0;
		}
		void Print(void){
			//这当然是输出呀 
			static char str[maxn];
			Assign(str);
			printf("%s\n",str);
		}
		void rader_trf(void){
			//雷德变换
			int j=0,k;
			for(int i=0;i<n;i++){
				if(j>i) swap(s[i],s[j]);
				k=n;
				while(j&(k>>=1)) j&=~k;
				j|=k;
			}
		}
		void FFT(bool type){
			//type=1为DFT求值(系数表达式转点值表达式)
			//type=0为IDFT求插值(点值表达式转系数表达式)
			rader_trf();
			double pi=type?PI:-PI;//IDFT 兀变负
			Complex w0;
			for(int step=1;step<n;step<<=1){
				//相邻两个长度为step的点值表达式合并 
				for(int H=0;H<n;H+=step<<1){
					//将[H,H+step)和[H+step,H+2*step)两个点值表达式合并
					double alpha = pi/step;//2*step次单位根,转动的角度为alpha的倍数
					Complex wn(cos(alpha),sin(alpha)),wk(1.0,0.0);
					for(int k=0;k<step;k++){
						int Ek=H+k;
						int Ok=H+k+step;
						Complex t=wk*s[Ok];
						s[Ok]=s[Ek]-t;
						s[Ek]=s[Ek]+t;
						wk=wk*wn;
					}
				}
			}
			if(!type) for(int i=0;i<n;i++) s[i]=s[i]/n;//IDFT 除以n 
		}
		void operator *= (Poly &b){
			int S=1;while(S<n+b.n) S<<=1;
			n=b.n=S;
			FFT(true);
			b.FFT(true);
			for(int i=0;i<n;i++) s[i]=s[i]*b.s[i];
			FFT(false); 
		}
};
Poly A,B;
int main()
{
	freopen("bettermul.in","r",stdin);
	freopen("bettermul.out","w",stdout);
	A.read();
	B.read();
	A*=B;
	A.Print();
	return 0;
}