代码

//Author:ObsidianY
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define In inline
#define INF 0x3f3f3f3f
#define For(i, a, b) for(register int i = a; i <= b; ++i)
#define foR(i, a, b) for(register int i = a; i >= b; --i)
#define ms memset
#define mc memcpy
#define pb push_back
#define mp make_pair
#define sz size
#define fi first
#define se second
#define pii pair < int, int >
#define debug(x) cerr << #x << " = " << x << endl
#define err cerr<<"Error\n"
#define GT cerr << 1.000 * clock() / CLOCKS_PER_SEC << endl;
#define file(FILE_NAME) freopen(FILE_NAME".in", "r", stdin), freopen(FILE_NAME".out", "w", stdout)

const int N = 3e6 + 10, P = 998244353, g = 3, ig = 332748118;
int n, m, len = 1, L;
int a[N], b[N], p[N], sum[N];
char s1[N], s2[N];
inline int read()
{
    int x = 0, f = 1, ch = getchar();
    while(ch < '0' || ch > '9') { if(ch == '-') f = -1; ch = getchar(); }
    while(ch >= '0' && ch <= '9') x = x * 10 + ch - 48, ch = getchar();
    return x * f;
}
int qpow(int A, int B)
{
    int res = 1;
    while(B)
    {
        if(B & 1) res = 1ll * res * A % P;
        A = 1ll * A * A % P;
        B >>= 1;
    }
    return res;
}
void NTT(int *A, int opt)
{
    For(i, 0, len - 1) if(i < p[i]) swap(A[i], A[p[i]]);
    for(int i = 1; i < len; i <<= 1)
    {
        int W = qpow(opt == 1 ? g : ig, (P - 1) / (i << 1));
        for(int j = 0; j < len; j += (i << 1))
        {
            int w = 1;
            for(int k = 0; k < i; ++k, w = w * W % P)
            {
                int x = A[j + k], y = w * A[j + k + i] % P;
                A[j + k] = (x + y) % P, A[j + k + i] = (x - y + P) % P;
            }
        }
    }
    return;
}
signed main()
{
    scanf("%s", s1); scanf("%s", s2);
    n = strlen(s1) - 1, m = strlen(s2) - 1;
    For(i, 0, n) a[i] = (s1[n - i] - '0' + P) % P; For(i, 0, m) b[i] = (s2[m - i] - '0' + P) % P;
    while(len <= n + m) len <<= 1, ++L;
    For(i, 0, len - 1) p[i] = (p[i >> 1] >> 1) | ((i & 1) << (L - 1));
    NTT(a, 1), NTT(b, 1);
    For(i, 0, len - 1) a[i] = a[i] * b[i] % P;
    NTT(a, -1);
    int inv = qpow(len, P - 2);
    For(i, 0, n + m) sum[i] = (a[i] * inv) % P;
    int top = 0;
    For(i, 0, len - 1)
    {
        if(sum[i] >= 10) top = i + 1, sum[i + 1] += sum[i] / 10, sum[i] %= 10;
        if(sum[i]) top = max(top, i);
    }
    while(sum[top] >= 10) sum[top + 1] += sum[top] / 10, sum[top] %= 10, ++top;
    foR(i, top, 0) printf("%lld", sum[i]);
    #define _ 0
    return 0 ^_^ 0;
    #undef _
}

评测结果