代码

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
 
#define RG register
#define IL inline
#define ll long long
#define ld long double
#define ui unsigned int
#define ull unsigned long long
#define LL long long
#define FILE
//#define DEBUG
 
namespace stdoier
{
template <typename T>
IL T max(RG const T &a, RG const T &b)
{
    if (a > b)
        return a;
    else
        return b;
}
 
template <typename T>
IL T min(RG const T &a, RG const T &b)
{
    if (a < b)
        return a;
    else
        return b;
}
 
template <typename T>
IL void cmin(RG T &a, RG const T &b)
{
    if (a > b)
        a = b;
}
 
template <typename T>
IL void cmax(RG T &a, RG const T &b)
{
    if (a < b)
        a = b;
}
} // namespace stdoier
 
using namespace stdoier;
 
namespace io
{
const int MaxBuff = 1 << 15;
const int MaxOut = 1 << 24;
char b[MaxBuff], *S = b, *T = b;
 
#define getc() (S == T && (T = (S = b) + fread(b, 1, MaxBuff, stdin), S == T) ? 0 : *S++)
 
template <class Type>
IL Type read()
{
    RG char ch;
    RG Type ans = 0;
    RG bool neg = 0;
    while (ch = getc(), (ch < '0' || ch > '9') && ch != '-')
        ;
    ch == '-' ? neg = 1 : ans = ch - '0';
    while (ch = getc(), '0' <= ch && ch <= '9')
        ans = ans * 10 + ch - '0';
    return neg ? -ans : ans;
}
 
IL int gets(RG char *s)
{
    RG char *iter = s;
    while (*iter = getc(), *iter == ' ' || *iter == '\n' || *iter == '\r')
        ;
    while (*++iter = getc(), *iter && *iter != ' ' && *iter != '\n' && *iter != '\r')
        ;
    *iter = 0;
    return iter - s;
}
 
char buff[MaxOut], *iter = buff;
 
template <class T>
IL void writeln(RG T x, RG char ch = '\n')
{
    static int stack[110];
    RG int O = 0;
    RG char *iter = io::iter;
    if (!x)
        *iter++ = '0';
    else
    {
        (x < 0) ? x = -x, *iter++ = '-' : 1;
        for (; x; x /= 10)
            stack[++O] = x % 10;
        for (; O; *iter++ = '0' + stack[O--])
            ;
    }
    *iter++ = ch, io::iter = iter;
}
 
template <class T>
IL void write(RG T x)
{
    static int stack[110];
    RG int O = 0;
    RG char *iter = io::iter;
    if (!x)
        *iter++ = '0';
    else
    {
        (x < 0) ? x = -x, *iter++ = '-' : 1;
        for (; x; x /= 10)
            stack[++O] = x % 10;
        for (; O; *iter++ = '0' + stack[O--])
            ;
    }
    io::iter = iter;
}
 
IL void puts(RG const char *s)
{
    while (*s)
        *iter++ = *s++;
}
 
struct Output
{
    ~Output() { fwrite(buff, 1, iter - buff, stdout), iter = buff; }
} output_hlpr;
} // namespace io
 
namespace solve_the_problem
{
int (*in)() = io ::read<int>;
const int N = 1e6 + 5;
const int P = 998244353;
 
int n, nn, rev[N << 2], a[N << 2], b[N << 2], w[N << 2];
char x[N], y[N];
 
inline int qpow(int a, int b)
{
    int ans = 1;
    for (; b; b >>= 1, a = ((ll)a * a) % P)
        if (b & 1)
            ans = ((ll)ans * a) % P;
    return ans;
}
 
void ntt(int n, int *a)
{
    for (int i = 0; i < n; ++i)
        if (i < rev[i])
            std ::swap(a[i], a[rev[i]]);
    for (int step = 1, ws = n / 2; step < n; step *= 2, ws /= 2)
        for (int j = 0; j < n; j += step * 2)
            for (int k = j, wn = 0; k < j + step; ++k, wn += ws)
            {
                int x = a[k], y = ((ll)a[k + step] * w[wn]) % P;
                a[k] = (x + y) % P, a[k + step] = (x - y + P) % P;
            }
}
 
void main()
{
    nn = 1e6, io ::gets(x), io ::gets(y);
    for (n = 1; n <= nn * 2; n <<= 1)
        ;
    for (int i = 0; i < nn; ++i)
        a[i] = x[nn - i - 1] - '0', b[i] = y[nn - i - 1] - '0';
    for (int i = 0; i < n; ++i)
        if (i & 1)
            rev[i] = rev[i - 1] + n / 2;
        else
            rev[i] = rev[i / 2] / 2;
    int gn = qpow(3, (P - 1) / n);
    for (int i = 0, j = 1; i < n; ++i)
        w[i] = j, j = ((ll)j * gn) % P;
    ntt(n, a), ntt(n, b);
    for (int i = 0; i < n; ++i)
        a[i] = ((ll)a[i] * b[i]) % P;
    gn = qpow(gn, P - 2);
    for (int i = 0, j = 1; i < n; ++i)
        w[i] = j, j = ((ll)j * gn) % P;
    ntt(n, a);
    for (int i = 0, inv = qpow(n, P - 2); i < n; i++)
        a[i] = ((ll)a[i] * inv) % P;
    for (int i = 0; i < n; ++i)
        if (a[i] > 10)
            a[i + 1] += a[i] / 10, a[i] %= 10;
    while (a[n] == 0 && n)
        --n;
    for (int i = n; i > 0; --i)
        io ::write(a[i]);
    io ::writeln(a[0]);
}
} // namespace solve_the_problem
 
int main()
{
    solve_the_problem ::main();
 
    return 0;
}

评测结果