比赛 |
清华集训2017模板练习 |
评测结果 |
AAAAAAAAAA |
题目名称 |
超强的乘法问题 |
最终得分 |
100 |
用户昵称 |
栋霸霸 |
运行时间 |
1.941 s |
代码语言 |
C++ |
内存使用 |
51.81 MiB |
提交时间 |
2017-07-17 14:21:56 |
显示代码纯文本
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <string>
#include <vector>
#include <cmath>
#include <complex>
using namespace std;
const int N=1000000;
typedef complex<double> c;
c F[N],A[N],B[N];
char a[N],b[N];
int ans[N];
int rev(int x,int n)
{
int ret=0;
for(int i=0; (1<<i)<n; i++)ret=(ret<<1)|((x&(1<<i))>0);
return ret;
}
void fft(c *a,int n,int f)
{
for(int i=0; i<n; i++)F[rev(i,n)]=a[i];
for(int i=2; i<=n; i*=2)
{
c wn=c(cos(2*acos(-1)*f/i),sin(2*acos(-1)*f/i));
for(int j=0; j<n; j+=i)
{
c w=1;
for(int k=j; k<j+i/2; k++)
{
c u=F[k],t=w*F[k+i/2];
F[k]=u+t;
F[k+i/2]=u-t;
w*=wn;
}
}
}
for(int i=0; i<n; i++)a[i]=(F[i]/=(f==-1?n:1));
}
int main()
{
freopen("bettermul.in","r",stdin);
freopen("bettermul.out","w",stdout);
scanf("%s%s",a,b);
int l1=strlen(a),l2=strlen(b),n1=1,n2=1,n=1;
while(n1<=l1)n1*=2;
while(n2<=l2)n2*=2;
while(n<2*max(n1,n2))n*=2;
for(int i=0; i<n; i++)A[i]=(i<l1?a[l1-i-1]-'0':0);
for(int i=0; i<n; i++)B[i]=(i<l2?b[l2-i-1]-'0':0);
fft(A,n,1);
fft(B,n,1);
for(int i=0; i<n; i++)A[i]*=B[i];
fft(A,n,-1);
for(int i=0; i<n; i++)ans[i]=int(A[i].real()+0.5);
for(int i=0; i<n-1; i++)ans[i+1]+=ans[i]/10,ans[i]%=10;
bool f=0;
for(int i=n-1; i>=0; i--)ans[i]?printf("%d",ans[i]),f=1:f||!i?printf("0"):0;
}