比赛 |
清华集训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;
}