P1919 【模板】A*B Problem升级版（FFT快速傅里叶）

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
using namespace std;
#define mp make_pair
#define fi first
#define se second
#define lson now<<1
#define rson now<<1|1
typedef long long ll;
const int maxn=6e6+5;
const double PI=acos(-1.0);
struct complx
{
    double x,y;
    complx(double xx=0,double yy=0)
    {
        x=xx; y=yy;
    }
}a[maxn],b[maxn];
complx operator + (complx a,complx b)
{
    return complx(a.x+b.x,a.y+b.y);
}
complx operator - (complx a,complx b)
{
    return complx(a.x-b.x,a.y-b.y);
}
complx operator * (complx a,complx b)
{
    return complx(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x);
}
char s1[maxn],s2[maxn];
int r[maxn],len1,len2,lim=1,l;
void fft(complx *A,int op)
{
    for(int i=0;i<lim;i++)
        if(r[i]>i)
            swap(A[i],A[r[i]]);
    for(int i=1;i<lim;i<<=1)
    {
        complx Wn(cos(PI/i),op*sin(PI/i));
        for(int R=i<<1,j=0;j<lim;j+=R)
        {
            complx w(1,0);
            for(int k=0;k<i;k++,w=w*Wn)
            {
                complx x=A[j+k],y=w*A[j+k+i];
                A[j+k]=x+y;
                A[j+k+i]=x-y;
            }
        }
    }
}
int ans[maxn];
int main()
{
    freopen("a.in","r",stdin);
    freopen("a.out","w",stdout);
    scanf("%s%s",s1,s2);
    len1=strlen(s1),len2=strlen(s2);
    for(int i=len1-1,j=0;i>=0;i--,j++) a[j].x=s1[i]-‘0‘;
    for(int i=len2-1,j=0;i>=0;i--,j++) b[j].x=s2[i]-‘0‘;
    while(lim<=(len1+len2)) lim<<=1,l++;
    for(int i=0;i<lim;i++)
        r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    fft(a,1); fft(b,1);
    for(int i=0;i<lim;i++) a[i]=a[i]*b[i];
    fft(a,-1);
    for(int i=0;i<lim;i++)
        ans[i]=(int)(a[i].x/lim+0.5);
    for(int i=0;i<lim;i++)
    {
        if(ans[i]>=10)
            ans[i+1]+=ans[i]/10,ans[i]%=10,lim+=(lim==i-1);
    }  
    for(int i=lim;i>=0;i--)
    {
        if(ans[i]) break;
        lim--;
    }
    for(int i=lim;i>=0;i--) printf("%d",ans[i]);
    return 0;
}