比赛 清华集训2017模板练习 评测结果 AAAAAAAEEE
题目名称 超强的乘法问题 最终得分 70
用户昵称 泪寒之雪 运行时间 0.363 s
代码语言 C++ 内存使用 15.10 MiB
提交时间 2017-12-02 20:17:17
显示代码纯文本
#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 378123
#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("bettermul.in","r",stdin);
	freopen("bettermul.out","w",stdout);
//0freopen("a.in","r",stdin);
	scanf("%s",ch);
	n=strlen(ch);
	n--;
	fo(i,0,n) a[i].r=ch[n-i]-48;
	m=max(n+1,m);
	scanf("%s",ch);
	n=strlen(ch);
	n--;
	fo(i,0,n) b[i].r=ch[n-i]-48;
	m=max(n+1,m);
	m<<=1;
	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;
}