比赛 清华集训2017模板练习 评测结果 AAAAAAAAAA
题目名称 超强的乘法问题 最终得分 100
用户昵称 FoolMike 运行时间 0.798 s
代码语言 C++ 内存使用 18.31 MiB
提交时间 2017-07-17 17:08:47
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1<<20|1,p=119<<23|1;
int inc(int x,int y){x+=y;return x>=p?x-p:x;}
int dec(int x,int y){x-=y;return x<0?x+p:x;}
int mul(int x,int y){return (ll)x*y%p;}
int power(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=mul(x,x))
		if (y&1) ans=mul(ans,x);
	return ans;
}
int w[N],iw[N];
void init(int n){
	w[0]=1;w[1]=power(3,(p-1)/n);
	for (int i=2;i<=n;i++) w[i]=mul(w[i-1],w[1]);
	for (int i=0;i<=n;i++) iw[i]=w[n-i];
}
void fft(int n,int *a,int *w){
	for (int i=0,j=0;i<n;i++){
		if (i<j) swap(a[i],a[j]);
		for (int k=n>>1;(j^=k)<k;k>>=1);
	}
	for (int i=2;i<=n;i<<=1){
		int m=i>>1,step=n/i;
		for (int j=0;j<n;j+=i)
		for (int k=0,pos=0;k<m;k++,pos+=step){
			int t=mul(a[j+k+m],w[pos]);
			a[j+k+m]=dec(a[j+k],t);
			a[j+k]=inc(a[j+k],t);
		}
	}
}
int n,m,a[N],b[N];
char s[N],t[N];
int main()
{
	freopen("bettermul.in","r",stdin);
	freopen("bettermul.out","w",stdout);
	scanf("%s%s",s,t);
	n=strlen(s);
	m=strlen(t);
	for (int i=0;i<n;i++) a[i]=s[n-i-1]-'0';
	for (int i=0;i<m;i++) b[i]=t[m-i-1]-'0';
	int size=1;
	while (size<=n+m) size<<=1;
	init(size);
	fft(size,a,w);fft(size,b,w);
	for (int i=0;i<size;i++) a[i]=mul(a[i],b[i]);
	fft(size,a,iw);
	int del=power(size,p-2);
	for (int i=0;i<size;i++) a[i]=mul(a[i],del);
	for (int i=0;i<size;i++)
		a[i+1]+=a[i]/10,a[i]%=10;
	int p=size-1;
	while (p&&!a[p]) p--;
	for (;p>=0;putchar(a[p--]+'0'));
	return 0;
}