代码

#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;

#define oo 1000000000
#define mp make_pair
#define fi first
#define se second
#define debug(...) fprintf(stderr, __VA_ARGS__), fflush(stderr)
#define FO(i,a,b) for(int i=a;i<=b;++i)
#define FD(i,a,b) for(int i=a;i>=b;--i)
#define FE(i,G,x) for(int i=G.h[x];i!=-1;i=G.v[i].nxt)
typedef long long LL;
typedef pair<int, int> PII;

template <class T> inline bool chkmin(T& x, T y) { return x > y ? x = y, true : false; }
template <class T> inline bool chkmax(T& x, T y) { return x < y ? x = y, true : false; }

template <class T> T reads() {
    T x = 0;
    static int f;
    static char c;
    for (f = 1; !isdigit(c = getchar()); ) if (c == '-') f = -1;
    for (x = 0; isdigit(c); c = getchar()) x = x * 10 + c - 48;
    return x * f;
}
#define read   reads<int>
#define readll reads<LL>

#define pi acos(-1)

struct comp{
    double a,b;
    comp(){}
    comp(double _a,double _b):a(_a),b(_b){}
    comp operator + (const comp& o){ return comp(a+o.a,b+o.b); }
    comp operator - (const comp& o){ return comp(a-o.a,b-o.b); }
    comp operator * (const comp& o){ return comp(a*o.a-b*o.b,a*o.b+b*o.a); }
};

int n,m,t,L,R[500005],d[500005];
comp a[500005],b[500005],c[500005];

void fft(comp* a,int x){
    FO(i,0,m-1) if(i<R[i]) swap(a[i],a[R[i]]);
    for (int s=2;s<=m;s<<=1){
        comp w0=comp(cos(2*pi/s),x*sin(2*pi/s));
        for (int k=0;k<m;k+=s){
            comp w=comp(1,0);
            FO(j,0,s/2-1){
                comp t=w*a[k+j+s/2],u=a[k+j];
                a[k+j]=u+t;a[k+j+s/2]=u-t;
                w=w*w0;
            }
        }
    }
    if (x==-1) FO(i,0,m-1) a[i].a/=m;
}
char ss[500005];
int main(void){
    n=read();t=n;m=1;
    scanf("%s",ss);FO(i,0,n-1) a[n-i-1]=comp(ss[i]-'0',0);
    scanf("%s",ss);FO(i,0,t-1) b[t-i-1]=comp(ss[i]-'0',0);
    n=n*2;t=t*2;while (m<=max(n,t)) m<<=1,L++;
    FO(i,0,m-1) R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));

    fft(a,1);fft(b,1);
    FO(i,0,m-1) c[i]=a[i]*b[i];
    fft(c,-1);
    FO(i,0,m-1) d[i]=(int)(c[i].a+0.1);
    FO(i,0,m-1) { d[i+1]+=d[i]/10,d[i]%=10; if (d[i+1]) m=max(m,i)+1; }
    while (!d[m-1]) m--;
    FD(i,m-1,0) putchar(d[i]+'0');
    return 0;
}

评测结果