HDU 1402 A * B Problem Plus 快速傅里叶变换 FFT 多项式

http://acm.hdu.edu.cn/showproblem.php?pid=1402

快速傅里叶变换优化的高精度乘法。

https://blog.csdn.net/ggn_2015/article/details/68922404 这个写的很详细了。

 #include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<iostream>
#include<vector>
#include<complex>
using namespace std;
#define LL long long
const int maxn=;
typedef complex< double >cd;
char s1[maxn]={},s2[maxn]={};
int ans[maxn]={};
int rev[maxn]={}; int s,bit;
cd a[maxn]={},b[maxn]={};
double Pi;
inline void getrev(){ for(int i=;i<s;i++)rev[i]=(rev[i>>]>>)|((i&)<<(bit-)); }
inline void fft(cd *c,int n,int dft){
for(int i=;i<=s;i++)if(rev[i]>i)swap(c[i],c[rev[i]]);
for(int step=;step<n;step<<=){
cd shu=exp(cd(,dft*Pi/step));
for(int i=;i<n;i+=step<<){
cd z=cd(,);
for(int j=i;j<i+step;j++){
cd x=c[j];cd y=c[j+step]*z;
c[j]=x+y; c[j+step]=x-y;
z*=shu;
}
}
}
if(dft==-)for(int i=;i<n;i++)c[i]/=n;
}
int main(){
cd cle(,);Pi=2.0*acos(0.0);
while(~scanf("%s%s",s1,s2)){
memset(rev,,sizeof(rev));
int l1=strlen(s1),l2=strlen(s2),n=l1+l2-;
bit=;s=; for(;s<n;++bit)s<<=;
getrev();
for(int i=;i<=s;i++){a[i]=cle;b[i]=cle;}
for(int i=;i<l1;i++)a[i]=(double)(s1[l1-i-]-'');
for(int i=;i<l2;i++)b[i]=(double)(s2[l2-i-]-'');
fft(a,s,);fft(b,s,);
for(int i=;i<s;i++)a[i]*=b[i];
fft(a,s,-);
memset(ans,,sizeof(ans));
for(int i=;i<s;i++){
ans[i]+=(int)(a[i].real()+0.5);
ans[i+]+=ans[i]/;
ans[i]%=;
}
int i;
for(i=l1+l2;!ans[i]&&i>;--i);
if(i==)printf("%d\n",ans[]);
else{
for(;i>=;--i)printf("%d",ans[i]);
printf("\n");
}
}
return ;
}
上一篇:对 UDP 的一些思考


下一篇:top的用法