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