代码

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int mod=998244353;
const int root=3;
int x,y;
ll qpow(ll a,ll b){
    ll res=1;
    while(b){
        if(b&1) res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}
int bitreverse(int x, int log_n) {
    int rev = 0;
    for (int i = 0; i < log_n; i++) {
        rev = (rev << 1) | ((x >> i) & 1);
    }
    return rev;
}
void ntt(vector<ll>& a,bool invert){
    int n=a.size();
    for(int i=0;i<n;i++){
        int rev=bitreverse(i,__lg(n));
        if(i<rev) swap(a[i],a[rev]);
    }
    for(int le=2;le<=n;le<<=1){
        int wl=qpow(root,(mod-1)/le);
        if(invert){
            wl=qpow(wl,mod-2);
        }
        for(int i=0;i<n;i+=le){
            ll w=1;
            for(int j=0;j<le/2;j++){
                ll u=a[i+j]%mod;
                ll v=a[i+j+le/2]*w%mod;
                a[i+j]=(u+v)%mod;
                a[i+j+le/2]=(u-v+mod)%mod;
                w=w*wl%mod;
            }
        }
    }
    if(invert){
        int inv=qpow(n,mod-2);
        for(int i=0;i<n;i++){
            a[i]=a[i]*inv%mod;
        }
    }
}
vector<ll> multiply(vector<ll> a,vector<ll> b){
    ll n=1;
    ll size=a.size()+b.size()-1;
    while(n<size) n<<=1;
    a.resize(n);
    b.resize(n);
    ntt(a,false);
    ntt(b,false);
    for(ll i=0;i<n;i++){
        a[i]=a[i]*b[i]%mod;
    }
    ntt(a,true);
    a.resize(size);
    for(int i=a.size()-1;i>0;i--){
        if(a[i]>9){
            a[i-1]+=a[i]/10;
            a[i]%=10;
        }
    }
    while(a[0]>9){
        a.insert(a.begin(),a[0]/10);
        a[1]%=10;
    }
    while(a.front()==0&&a.size()>1){
        a.erase(a.begin());
    }
    return a;
}
int main(){
    string n,m;
    cin >>n>>m;
    x=n.size(),y=m.size();
    vector<ll> poly1(x);
    vector<ll> poly2(y);
    for(int i=0;i<x;i++){
        poly1[i]=n[i]-'0';
    }
    for(int j=0;j<y;j++){
        poly2[j]=m[j]-'0';
    }
    vector<ll> ans=multiply(poly1,poly2);
    for(ll i=0;i<ans.size();i++){
        cout <<ans[i];
    }
    return 0;
}

评测结果