学会了FFT之后感觉自己征服了世界!
当然是幻觉...
不过FFT还是很有用的,在优化大规模的动规问题的时候有极大效果.
一般比较凶残的计数动规题都需要FFT(n<=1e9).
下面是高精度乘法的板子.
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<iomanip>
using namespace std;
#define LL long long
#define up(i,j,n) for(int i=j;i<=n;i++)
#define pii pair<int,int>
#define db double
#define eps 1e-4
#define FILE "dealing"
int read(){
int x=0,f=1,ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch<='9'&&ch>='0'){x=(x<<1)+(x<<3)+ch-'0',ch=getchar();}
return x*f;
}
const int maxn=401000,inf=1000000000000000LL,limit=20000,mod=9973;
bool cmin(int& a,int b){return a>b?a=b,true:false;}
bool cmax(int& a,int b){return a<b?a=b,true:false;}
namespace FFT{
int ans[maxn];
db pi=(acos(-1.0));
struct cp{
db x,y;
cp(db x=0,db y=0):x(x),y(y){}
inline cp operator+(const cp& b){return cp(x+b.x,y+b.y);}
inline cp operator-(const cp& b){return cp(x-b.x,y-b.y);}
inline cp operator*(const cp& b){return cp(x*b.x-y*b.y,x*b.y+y*b.x);}
}w[maxn],a[maxn],b[maxn];
int L,H,R[maxn];
inline void swap(cp& x,cp& y){cp t(x);x=y;y=t;}
void FFT(cp* a,int f){
up(i,0,L-1)if(i<R[i])swap(a[i],a[R[i]]);
for(int len=2;len<=L;len<<=1){
int l=len>>1;
cp wn(cos(pi/l),f*sin(pi/l));
up(i,1,l-1)w[i]=w[i-1]*wn;
for(int st=0;st<L;st+=len){
for(int k=0;k<l;k++){
cp x=a[st+k],y=w[k]*a[st+k+l];
a[st+k]=x+y,a[st+k+l]=x-y;
}
}
}
if(f==-1)up(i,0,L-1)a[i].x/=L;
}
void prepare(){
w[0].x=1;
up(i,0,L)R[i]=(R[i>>1]>>1)|((i&1)<<(H-1));
}
void solve(int* c,int *d,int n,int m,int* ch){
up(i,0,n-1)a[i].x=c[i+1],a[i].y=0;
up(i,0,m-1)b[i].x=d[i+1],b[i].y=0;
n++,m++;
for(H=0,L=1;L<n+m-1;H++)L<<=1;
prepare();
FFT(a,1);FFT(b,1);
up(i,0,L-1)a[i]=a[i]*b[i];
FFT(a,-1);
up(i,0,n+m-2)ch[i+1]=(int)(a[i].x+0.5);
return;
}
};
char s[maxn];
int a[maxn],b[maxn],n,m,ans[maxn];
int main(){
freopen(FILE".in","r",stdin);
freopen(FILE".out","w",stdout);
scanf("%s",s+1);
n=strlen(s+1);
for(int i=1;i<=n;i++)a[i]=s[n-i+1]-'0';
scanf("%s",s+1);
m=strlen(s+1);
for(int i=1;i<=m;i++)b[i]=s[m-i+1]-'0';
FFT::solve(a,b,n,m,ans);
int len=n+m;
for(int i=1;i<=len;i++)if(ans[i]>=10)ans[i+1]+=ans[i]/10,ans[i]%=10;
while(ans[len]>=10)ans[len+1]+=ans[len]/10,ans[len]%=10,len++;
while(!ans[len]&&len>1)len--;
for(int i=len;i>=1;i--)printf("%d",ans[i]);
return 0;
}