记录编号	227111	评测结果	AAAAAAAAAA
题目名称	超强的乘法问题	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	3.379 s
提交时间	2016-02-18 15:09:09	内存使用	9.39 MiB

#define maxs 21ul
#define maxn 530010ul

#include <stdio.h>
#include <string.h>
#include <algorithm>

typedef long long ll;
const ll P=(479<<21)+1,G=3;
int n,len1,len2,tot;
ll wn_pre[maxs],A[maxn],B[maxn];
char s1[maxn],s2[maxn];

inline ll ksm(ll p,ll k,ll mod){
	ll ans=1;
	while(k){
		if(k&1) (ans*=p)%=mod;
		k>>=1,(p*=p)%=mod;
	}
	return ans;
}

inline void getwn(){
	for(int i=0;i<maxs;i++)
		wn_pre[i]=ksm(G,(P-1)/(1<<i),P);
	return;
}

inline void fnt(ll *a,int flag){
	for(int i=0,j=0;i<n;i++){
		if(i>j) std::swap(a[i],a[j]);
		for(int t=n>>1;(j^=t)<t;t>>=1);
	}
	ll wn,w,t,u;
	for(int m=2,h=1;m<=n;h++,m<<=1){
		wn=wn_pre[h],w=1;
		for(int i=0;i<n;i+=m,w=1) for(int k=0,p=m>>1;k<p;k++,(w*=wn)%=P)
		    t=(w*a[i+k+p])%P,u=a[i+k],a[i+k]=(u+t)%P,a[i+k+p]=(u-t)%P;
	}
	if(flag==-1){
		for(int i=1,r=n/2;i<r;i++) std::swap(a[i],a[n-i]);
		ll inv=ksm(n,P-2,P);
		for(int i=0;i<n;i++) (a[i]*=inv)%=P;
	}
	return;
}

int main(){
	freopen("bettermul.in","r",stdin);
	freopen("bettermul.out","w",stdout);
	getwn(),scanf("%s%s",s1,s2);
	len1=strlen(s1),len2=strlen(s2);
	tot=len1>len2?len1:len2;
	for(int i=len1-1;~i;--i) A[len1-i-1]=s1[i]-48;
	for(int i=len2-1;~i;--i) B[len2-i-1]=s2[i]-48;
	for(n=1;n<(tot<<1);n<<=1);
	fnt(A,1),fnt(B,1);
	for(int i=0;i<n;i++) (A[i]*=B[i])%=P;
	fnt(A,-1);
	for(int i=0;i<n;i++) ((A[i]%=P)+=P)%=P;
	for(int i=0;i<n;i++) if(A[i]>9) A[i+1]+=A[i]/10,A[i]%=10;
	len1+=len2-1;
	if(A[len1]) len1++;
	for(int i=len1-1;~i;--i) putchar(A[i]+48);
	return 0;
}