```cpp
#include<bits/stdc++.h>
using namespace std;
#define MN 60060
#define db double
const db pi=acos(-1.0);
struct cpx{
db x,y;
cpx(db xx=0,db yy=0){x=xx,y=yy;}
}a[MN],b[MN];
cpx operator + (cpx a,cpx b){ return cpx(a.x+b.x , a.y+b.y);}
cpx operator - (cpx a,cpx b){ return cpx(a.x-b.x , a.y-b.y);}
cpx operator * (cpx a,cpx b){ return cpx(a.x*b.x-a.y*b.y , a.x*b.y+a.y*b.x);}
int c[MN],tta,ttb;
void FFT(int limit,cpx *a,int emm)
{
if(limit==1) return ;
cpx a1[limit>>1],a2[limit>>1];
for(int i=0;i<=limit;i+=2) a1[i>>1]=a[i],a2[i>>1]=a[i+1];
FFT(limit>>1,a1,emm);FFT(limit>>1,a2,emm);
cpx wn=cpx(cos(2.0*pi/limit),emm*sin(2.0*pi/limit)),w=cpx(1,0);
for(int i=0;i<(limit>>1);i++,w=w*wn)
{
a[i]=a1[i]+w*a2[i];
a[i+(limit>>1)]=a1[i]-w*a2[i];
}
}
int main()
{
int n;char s1[MN],s2[MN];
scanf("%d%s%s",&n,&s1,&s2);
for(int i=n-1;i>=0;i--) a[tta++].x=s1[i]-'0';
for(int i=n-1;i>=0;i--) b[ttb++].x=s2[i]-'0';
int limit=1;while(limit<=2*n) limit<<=1;
FFT(limit,a,1);FFT(limit,b,1);
for(int i=0;i<=limit;i++) a[i]=a[i]*b[i];
FFT(limit,a,-1);
for(int i=0;i<=limit;i++)
{
c[i]+=(int) (a[i].x/limit+0.5);
if(c[i]>9)
{
c[i+1]+=c[i]/10;c[i]%=10;if(i==limit) limit++;
}
}
while(c[limit]==0) limit--;
for(int i=limit;i>=0;i--) printf("%d",c[i]);
return 0;
}
```
by LittlePrincess @ 2018-02-23 20:27:43
不是单纯看你递归次数,还要看你传的参,每次都下传个cpx数组会爆也不奇怪啊..
by sigland @ 2018-03-15 18:05:40
~~你开数组开小了。。。~~
题面上说的60000是数字长度，FFT怎么也得开2倍大小吧...
by nianheng @ 2018-03-27 08:10:50