代码

// 1004a 高精度乘法2 - 2-prime 30-bit NTT, base 1e7
#include <stdio.h>
#include <stdint.h>
#include <string.h>
#include <stdlib.h>

typedef uint32_t u32;
typedef uint64_t u64;

static const u32 M0 = 998244353u;
static const u32 M1 = 1004535809u;
static const u32 G0 = 3u, G1 = 3u;

static inline u64 powmod(u64 a, u64 e, u64 m){
    u64 r=1; a%=m;
    while(e){ if(e&1) r=(u64)((__uint128_t)r*a%m); a=(u64)((__uint128_t)a*a%m); e>>=1; }
    return r;
}

#define N 4096
static u32 A[N], B[N];
static u32 roots0[N], iroots0[N], roots1[N], iroots1[N];

template<u32 M>
static inline u32 mulmod(u32 a, u32 b){ return (u32)((u64)a * b % M); }

template<u32 M>
static void ntt_fwd(u32* a, const u32* w){
    for(int len=N; len>1; len>>=1){
        int half=len>>1, step=N/len;
        for(int i=0;i<N;i+=len){
            u32* base = a+i;
            int j=0;
            for(; j+3<half; j+=4){
                u32 u0=base[j],v0=base[j+half];
                u32 u1=base[j+1],v1=base[j+1+half];
                u32 u2=base[j+2],v2=base[j+2+half];
                u32 u3=base[j+3],v3=base[j+3+half];
                u32 s0=u0+v0; if(s0>=M)s0-=M;
                u32 d0=u0+M-v0; if(d0>=M)d0-=M;
                base[j]=s0; base[j+half]=mulmod<M>(d0, w[(j)*step]);
                u32 s1=u1+v1; if(s1>=M)s1-=M;
                u32 d1=u1+M-v1; if(d1>=M)d1-=M;
                base[j+1]=s1; base[j+1+half]=mulmod<M>(d1, w[(j+1)*step]);
                u32 s2=u2+v2; if(s2>=M)s2-=M;
                u32 d2=u2+M-v2; if(d2>=M)d2-=M;
                base[j+2]=s2; base[j+2+half]=mulmod<M>(d2, w[(j+2)*step]);
                u32 s3=u3+v3; if(s3>=M)s3-=M;
                u32 d3=u3+M-v3; if(d3>=M)d3-=M;
                base[j+3]=s3; base[j+3+half]=mulmod<M>(d3, w[(j+3)*step]);
            }
            for(; j<half; j++){
                u32 u=base[j],v=base[j+half];
                u32 s=u+v; if(s>=M)s-=M;
                u32 d=u+M-v; if(d>=M)d-=M;
                base[j]=s; base[j+half]=mulmod<M>(d, w[j*step]);
            }
        }
    }
}

template<u32 M>
static void ntt_inv(u32* a, const u32* w){
    for(int len=2; len<=N; len<<=1){
        int half=len>>1, step=N/len;
        for(int i=0;i<N;i+=len){
            u32* base = a+i;
            int j=0;
            for(; j+3<half; j+=4){
                u32 u0=base[j], v0=mulmod<M>(base[j+half], w[(j)*step]);
                u32 u1=base[j+1], v1=mulmod<M>(base[j+1+half], w[(j+1)*step]);
                u32 u2=base[j+2], v2=mulmod<M>(base[j+2+half], w[(j+2)*step]);
                u32 u3=base[j+3], v3=mulmod<M>(base[j+3+half], w[(j+3)*step]);
                u32 s0=u0+v0; if(s0>=M)s0-=M;
                u32 d0=u0+M-v0; if(d0>=M)d0-=M;
                base[j]=s0; base[j+half]=d0;
                u32 s1=u1+v1; if(s1>=M)s1-=M;
                u32 d1=u1+M-v1; if(d1>=M)d1-=M;
                base[j+1]=s1; base[j+1+half]=d1;
                u32 s2=u2+v2; if(s2>=M)s2-=M;
                u32 d2=u2+M-v2; if(d2>=M)d2-=M;
                base[j+2]=s2; base[j+2+half]=d2;
                u32 s3=u3+v3; if(s3>=M)s3-=M;
                u32 d3=u3+M-v3; if(d3>=M)d3-=M;
                base[j+3]=s3; base[j+3+half]=d3;
            }
            for(; j<half; j++){
                u32 u=base[j], v=mulmod<M>(base[j+half], w[j*step]);
                u32 s=u+v; if(s>=M)s-=M;
                u32 d=u+M-v; if(d>=M)d-=M;
                base[j]=s; base[j+half]=d;
            }
        }
    }
    u32 ninv = (u32)powmod(N, M-2, M);
    for(int i=0;i<N;i++) a[i] = mulmod<M>(a[i], ninv);
}

static char ibuf[30000];
static int ilen;
static char obuf[21000];
static int olen;
static char tab3[1000][4];
static void build_tab3(void){
    for(int i=0;i<1000;i++){ int v=i; tab3[i][2]='0'+v%10; v/=10; tab3[i][1]='0'+v%10; v/=10; tab3[i][0]='0'+v%10; }
}

int main(){
    build_tab3();
    {
        u32 w0 = (u32)powmod(G0, (M0-1)/N, M0);
        u32 w1 = (u32)powmod(G1, (M1-1)/N, M1);
        roots0[0]=1; for(int i=1;i<N;i++) roots0[i]=mulmod<M0>(roots0[i-1], w0);
        roots1[0]=1; for(int i=1;i<N;i++) roots1[i]=mulmod<M1>(roots1[i-1], w1);
        iroots0[0]=1; for(int i=1;i<N;i++) iroots0[i]=roots0[N-i];
        iroots1[0]=1; for(int i=1;i<N;i++) iroots1[i]=roots1[N-i];
    }

    ilen = fread(ibuf, 1, sizeof(ibuf), stdin);
    int pa=0;
    while(pa<ilen && (ibuf[pa]==' '||ibuf[pa]=='\n'||ibuf[pa]=='\r'||ibuf[pa]=='\t')) pa++;
    int a_start=pa; while(pa<ilen && ibuf[pa]!=' '&&ibuf[pa]!='\n'&&ibuf[pa]!='\r'&&ibuf[pa]!='\t') pa++;
    int a_end=pa; while(pa<ilen && (ibuf[pa]==' '||ibuf[pa]=='\n'||ibuf[pa]=='\r'||ibuf[pa]=='\t')) pa++;
    int b_start=pa; while(pa<ilen && ibuf[pa]!=' '&&ibuf[pa]!='\n'&&ibuf[pa]!='\r'&&ibuf[pa]!='\t') pa++;
    int b_end=pa;

    int sa=a_start; while(sa<a_end-1 && ibuf[sa]=='0') sa++;
    int sb=b_start; while(sb<b_end-1 && ibuf[sb]=='0') sb++;

    static u32 AL[1430], BL[1430];
    int na=0, nb=0;
    { int pos=a_end; while(pos>sa){ int st=pos-7; if(st<sa)st=sa; u32 v=0; for(int i=st;i<pos;i++) v=v*10+(ibuf[i]-'0'); AL[na++]=v; pos=st; } }
    { int pos=b_end; while(pos>sb){ int st=pos-7; if(st<sb)st=sb; u32 v=0; for(int i=st;i<pos;i++) v=v*10+(ibuf[i]-'0'); BL[nb++]=v; pos=st; } }

    u64 INV01 = powmod(M0 % M1, M1-2, M1);

    static u32 r0[N], r1[N];

    for(int i=0;i<N;i++){ A[i]=0; B[i]=0; }
    for(int i=0;i<na;i++) A[i]=AL[i]%M0;
    for(int i=0;i<nb;i++) B[i]=BL[i]%M0;
    ntt_fwd<M0>(A, roots0);
    ntt_fwd<M0>(B, roots0);
    for(int i=0;i<N;i++) A[i]=mulmod<M0>(A[i],B[i]);
    ntt_inv<M0>(A, iroots0);
    for(int i=0;i<N;i++) r0[i]=A[i];

    for(int i=0;i<N;i++){ A[i]=0; B[i]=0; }
    for(int i=0;i<na;i++) A[i]=AL[i]%M1;
    for(int i=0;i<nb;i++) B[i]=BL[i]%M1;
    ntt_fwd<M1>(A, roots1);
    ntt_fwd<M1>(B, roots1);
    for(int i=0;i<N;i++) A[i]=mulmod<M1>(A[i],B[i]);
    ntt_inv<M1>(A, iroots1);
    for(int i=0;i<N;i++) r1[i]=A[i];

    int outlen = na + nb - 1;
    u64 carry = 0;
    static u32 outlimbs[2860];
    int nout = 0;
    for(int i=0;i<outlen;i++){
        u64 c = r0[i];
        u64 d = (u64)r1[i] + M1 - c;
        if (d >= M1) d -= M1;
        u64 t = d * INV01 % M1;
        c += t * (u64)M0;
        c += carry;
        outlimbs[nout++] = (u32)(c % 10000000ULL);
        carry = c / 10000000ULL;
    }
    while(carry){ outlimbs[nout++] = (u32)(carry % 10000000ULL); carry /= 10000000ULL; }
    int hi = nout-1;
    while(hi>0 && outlimbs[hi]==0) hi--;

    {
        u32 v = outlimbs[hi];
        char tmp[9]; int t=0;
        do { tmp[t++]='0'+v%10; v/=10; } while(v);
        while(t>0) obuf[olen++] = tmp[--t];
    }
    for(int i=hi-1;i>=0;i--){
        u32 v = outlimbs[i];
        u32 g1 = v / 1000000;
        u32 g2 = (v/1000) % 1000;
        u32 g0 = v % 1000;
        obuf[olen++] = '0' + g1;
        const char* p = tab3[g2];
        obuf[olen++]=p[0]; obuf[olen++]=p[1]; obuf[olen++]=p[2];
        p = tab3[g0];
        obuf[olen++]=p[0]; obuf[olen++]=p[1]; obuf[olen++]=p[2];
    }
    obuf[olen++] = '\n';
    fwrite(obuf, 1, olen, stdout);
    return 0;
}

评测结果