这几天学习了FFT,第一道题就是高精度,存个板子记录一下。
//FFT multy
#include<set>
#include<map>
#include<vector>
#include<string>
#include<math.h>
#include<time.h>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#define N 300000
#define pi acos(-1)
#define ll long long
#define lowbit(x) (x&-x)
#define maxint 2147483647
#define abs(x) (a<0?-a:a)
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define ckmax(a,b) (a=max(a,b))
#define ckmin(a,b) (a=min(a,b))
#define isd(c) ('0'<=c&&c<='9')
using namespace std;
template<typename T> inline void read(T&x){T f=1;x=0;char c;
for (c=getchar(); !isd(c); c=getchar()) f=(c=='-')?-1:f;
for (; isd(c); c=getchar()) x=(x<<3)+(x<<1)+(c^48);x*=f;
}
template<typename T> inline void wt(T x,char c='\0'){char ch[(sizeof(T)+1)<<1];if (x<0) putchar('-'),x=-x;
int t=-1; do ch[++t]=x%10+'0',x/=10; while(x); do putchar(ch[t]); while(t--); if (c!='\0') putchar(c);
}
struct cpx {double r,i;cpx(){}
cpx(double x, double y) {r=x;i=y;}
inline cpx operator*(const cpx&x)const {return cpx(r*x.r-i*x.i,r*x.i+i*x.r );}
inline cpx operator*=(const cpx&x) {return*this=*this*x;}
inline cpx operator+(const cpx&x)const {return cpx(r+x.r,i+x.i);}
inline cpx operator-(const cpx&x)const {return cpx(r-x.r,i-x.i);}
} a[N],b[N];
int n,L,R[N],c[N];
char ch[N];
inline void fft(cpx*a,int f) {
for (int i=0;i<n;++i) if(i<R[i]) swap(a[i],a[R[i]]);
for(register int i=1; i<n; i<<=1) {
cpx wn(cos(pi/i),f*sin(pi/i));
for(register int j=0; j<n; j+=(i<<1)) {
cpx w(1,0);
for(register int k=0; k<i;++k,w*=wn) {
cpx x=a[j+k],y=w*a[j+k+i];
a[j+k]=x+y,a[j+k+i]=x-y;
}
}
}
if(f==-1) for (int i=0;i<n;++i) a[i].r/=n;
}
int main() {
read(n);n--;
scanf("%s",ch);for (int i=0;i<=n;++i) a[i].r=ch[n-i]-'0';
scanf("%s",ch);for (int i=0;i<=n;++i) b[i].r=ch[n-i]-'0';
int m=2*n;for(n=1; n<=m ; n<<=1)++L;
for (int i=0;i<n;++i) R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));
fft(a,1);fft(b,1);for (int i=0;i<=n;++i) a[i]*=b[i];fft(a,-1);
for (int i=0;i<=m;++i) c[i]=(int)(a[i].r+0.1);
for (int i=0;i<=m;++i) if(c[i]>=10) {
c[i+1]+=c[i]/10,c[i]%=10;if(i==m) m++;
}
while(m) if(c[m]) break;else m--;
while(~m) wt(c[m--]);putchar('\n');
return 0;
}
