代码

#include<algorithm>
#include<iostream>
using namespace std;
const int MAXN = 2.8e5, P = 998244353, G = 3;
int quick_pow(int a, int k)
{
    int ans = 1;
    while(k)
    {
        if(k & 1)
            ans = (long long)ans * a % P;
        a = (long long)a * a % P;
        k >>= 1;
    }
    return ans;
}
int len, rev[MAXN];
void init(int n)
{
    len = 1;
    while(len <= n)
        len <<= 1;
    for(int i=0;i<len;i++)
    {
        rev[i] = rev[i>>1]>>1;
        if(i & 1)
            rev[i] |= len >> 1;
    }
}
void change(int* a)
{
    for(int i=0;i<len;i++)
        if(i < rev[i])
            swap(a[i], a[rev[i]]);
}
void ntt(int* a, int mode)
{
    change(a);
    for(int bs=2;bs<=len;bs<<=1)
    {
        int wn = quick_pow(G, (P-1)/bs);
        for(int s=0;s<len;s+=bs)
        {
            int w = 1;
            for(int i=s;i<s+bs/2;i++)
            {
                int g = a[i], h = (long long)w*a[i+bs/2]%P;
                a[i] = (g+h)%P, a[i+bs/2] = (g-h+P)%P;
                w = (long long)w*wn%P;
            }
        }
    }
    if(mode == -1)
    {
        reverse(a+1,a+len);
        int inv = quick_pow(len, P-2);
        for(int i=0;i<len;i++)
            a[i] = (long long)a[i] * inv % P;
    }
}
int len1, len2;
int a[MAXN], b[MAXN];
char t;
int main()
{
    t = getc(stdin);
    while(t < '0' || t > '9')
        t = getc(stdin);
    while(t >= '0' && t <= '9')
    {
        a[len1++] = t - '0';
        t = getc(stdin);
    }
    while(t < '0' || t > '9')
        t = getc(stdin);
    while(t >= '0' && t <= '9')
    {
        b[len2++] = t - '0';
        t = getc(stdin);
    }
    reverse(a, a+len1), reverse(b, b+len2);
    init(len1+len2-2);
    ntt(a, 1), ntt(b, 1);
    for(int i=0;i<len;i++)
        a[i] = (long long)a[i] * b[i] % P;
    ntt(a, -1);
    for(int i=0;i<len;i++)
        if(a[i] >= 10)
            a[i+1] += a[i] / 10, a[i] %= 10;
    int r = MAXN-1;
    while(!a[r] && r > 0)r--;
    for(int i=r;i>=0;i--)
        putc(a[i] + '0', stdout);
    putc('\n', stdout);
}

评测结果