代码

#include<bits/stdc++.h>
#define fs first
#define sc second
#define pb push_back
using namespace std;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stdexcept>
using namespace std;
const int P = 998244353, G = 3;
long long qpow(long long a, long long b) { long long r=1; for(;b;b>>=1,a=a*a%P) if(b&1) r=r*a%P; return r; }
void ntt(vector<long long>& a, int inv) { int n=a.size(); for(int i=1,j=0;i<n;i++){ int b=n>>1; for(;j&b;b>>=1) j^=b; j^=b; if(i<j) swap(a[i],a[j]); } for(int l=2;l<=n;l<<=1){ long long wN=qpow(G,(P-1)/l); if(inv) wN=qpow(wN,P-2); for(int i=0;i<n;i+=l){ long long w=1; for(int j=0;j<l/2;j++,w=w*wN%P){ long long u=a[i+j],v=a[i+j+l/2]*w%P; a[i+j]=(u+v)%P; a[i+j+l/2]=(u-v+P)%P; } } } if(inv){ long long invN=qpow(n,P-2); for(long long& x:a) x=x*invN%P; } }
class BigInt {
public:
    vector<int> v; int sign;
    BigInt() : sign(0) {}
    BigInt(long long val) { sign=val>0?1:(val<0?-1:0); val=abs(val); while(val) { v.push_back(val%1000000000); val/=1000000000; } }
    BigInt(string s) { sign=1; if(s[0]=='-') { sign=-1; s=s.substr(1); } if(s=="0"||s.empty()) sign=0; for(int i=(int)s.length(); i>0; i-=9) { if(i<9) v.push_back(stoi(s.substr(0,i))); else v.push_back(stoi(s.substr(i-9,9))); } trim(); }
    void trim() { while(!v.empty() && v.back()==0) v.pop_back(); if(v.empty()) sign=0; }
    static int abs_cmp(const BigInt& a, const BigInt& b) { if(a.v.size()!=b.v.size()) return a.v.size()<b.v.size()?-1:1; for(int i=(int)a.v.size()-1;i>=0;--i) if(a.v[i]!=b.v[i]) return a.v[i]<b.v[i]?-1:1; return 0; }
    static int cmp(const BigInt& a, const BigInt& b) { if(a.sign!=b.sign) return a.sign<b.sign?-1:1; if(a.sign==0) return 0; return abs_cmp(a,b)*a.sign; }
    bool operator<(const BigInt& b) const { return cmp(*this,b)<0; }
    bool operator==(const BigInt& b) const { return cmp(*this,b)==0; }
    bool operator>(const BigInt& b) const { return b<*this; }
    bool operator<=(const BigInt& b) const { return !(b<*this); }
    bool operator>=(const BigInt& b) const { return !(*this<b); }
    bool operator!=(const BigInt& b) const { return !(*this==b); }
    static BigInt shift(BigInt a, int m) { if(a.sign==0) return a; if(m>0) a.v.insert(a.v.begin(),m,0); else if(m<0) { if(-m>=(int)a.v.size()) return BigInt(0); a.v.erase(a.v.begin(), a.v.begin()-m); } a.trim(); return a; }
    static BigInt add_abs(BigInt a, BigInt b) { BigInt c; c.sign=1; int carry=0; for(size_t i=0; i<max(a.v.size(),b.v.size())||carry; ++i) { carry+=(i<a.v.size()?a.v[i]:0)+(i<b.v.size()?b.v[i]:0); c.v.push_back(carry%1000000000); carry/=1000000000; } c.trim(); return c; }
    static BigInt sub_abs(BigInt a, BigInt b) { BigInt c; c.sign=1; int borrow=0; for(size_t i=0; i<a.v.size(); ++i) { borrow=a.v[i]-(i<b.v.size()?b.v[i]:0)-borrow; if(borrow<0) { c.v.push_back(borrow+1000000000); borrow=1; } else { c.v.push_back(borrow); borrow=0; } } c.trim(); return c; }
    BigInt operator+(const BigInt& b) const { if(sign==0) return b; if(b.sign==0) return *this; if(sign==b.sign) { BigInt c=add_abs(*this,b); c.sign=sign; return c; } if(abs_cmp(*this,b)>=0) { BigInt c=sub_abs(*this,b); c.sign=sign; return c; } BigInt c=sub_abs(b,*this); c.sign=b.sign; return c; }
    BigInt operator-() const { BigInt c=*this; c.sign=-c.sign; return c; }
    BigInt operator-(const BigInt& b) const { return *this+(-b); }
    static BigInt mul_naive(const BigInt& a, const BigInt& b) { BigInt c; c.sign=a.sign*b.sign; c.v.assign(a.v.size()+b.v.size(),0); for(size_t i=0; i<a.v.size(); ++i) for(size_t j=0; j<b.v.size(); ++j) { long long t=c.v[i+j]+1LL*a.v[i]*b.v[j]; c.v[i+j]=t%1000000000; c.v[i+j+1]+=t/1000000000; } c.trim(); return c; }
    static BigInt mul_karatsuba(BigInt a, BigInt b) { int m=min(a.v.size(),b.v.size())/2; if(m==0) return mul_naive(a,b); BigInt a0=a, a1=shift(a,-m), b0=b, b1=shift(b,-m); a0.v.resize(m); a0.trim(); b0.v.resize(m); b0.trim(); BigInt z0=a0*b0, z2=a1*b1, z1=(a0+a1)*(b0+b1)-z0-z2; return shift(z2,2*m)+shift(z1,m)+z0; }
    static BigInt mul_ntt(const BigInt& a, const BigInt& b) { vector<long long> A,B; for(int x:a.v){for(int i=0;i<9;++i){A.push_back(x%10);x/=10;}} for(int x:b.v){for(int i=0;i<9;++i){B.push_back(x%10);x/=10;}} int sz=1; while(sz<A.size()+B.size()) sz<<=1; A.resize(sz); B.resize(sz); ntt(A,0); ntt(B,0); for(int i=0;i<sz;++i) A[i]=A[i]*B[i]%P; ntt(A,1); BigInt c; c.sign=a.sign*b.sign; long long carry=0; int p[9]={1,10,100,1000,10000,100000,1000000,10000000,100000000}; for(size_t i=0;i<A.size()||carry;++i){ long long val=carry+(i<A.size()?A[i]:0); carry=val/10; val%=10; if(i%9==0) c.v.push_back(val); else c.v.back()+=val*p[i%9]; } c.trim(); return c; }
    BigInt operator*(const BigInt& b) const { if(sign==0||b.sign==0) return BigInt(0); if(v.size()<64||b.v.size()<64) return mul_naive(*this,b); if(v.size()<256||b.v.size()<256) return mul_karatsuba(*this,b); return mul_ntt(*this,b); }
    static BigInt div_naive(BigInt a, BigInt b) { if(b.sign==0) throw runtime_error("Div by 0"); BigInt q, r; q.sign=a.sign*b.sign; q.v.assign(a.v.size(),0); b.sign=1; for(int i=(int)a.v.size()-1; i>=0; --i) { r=shift(r,1); if(a.v[i]>0||r.sign) { if(!r.sign) r.v.assign(1,0); r.v[0]=a.v[i]; r.sign=1; r.trim(); } int low=0, high=1000000000-1, mid, ans=0; while(low<=high) { mid=low+(high-low)/2; if(abs_cmp(r, b*BigInt(mid))>=0) { ans=mid; low=mid+1; } else high=mid-1; } q.v[i]=ans; r=r-b*BigInt(ans); } q.trim(); return q; }
    static BigInt div_bz(BigInt a, BigInt b) { if(a.v.size()<b.v.size()) return BigInt(0); int k=b.v.size()/2; if(k==0) return div_naive(a,b); BigInt a1=shift(a,-k), a2=a; a2.v.resize(k); a2.trim(); BigInt q1=a1/b, r1=a1-q1*b; BigInt r1_a2=shift(r1,k)+a2; BigInt q2=r1_a2/b; return shift(q1,k)+q2; }
    static BigInt newton_inv(BigInt b, int k) { if(k<=2) { BigInt r; r.v.assign(2*k,0); r.v.back()=1; return div_naive(r,b); } int h=(k+1)/2; BigInt b_h=shift(b, h-k); BigInt z=newton_inv(b_h, h); return shift(z*BigInt(2), k-h) - shift(z*z*b_h, -2*h); }
    static BigInt div_newton(BigInt a, BigInt b) { int n=a.v.size(), m=b.v.size(); if(n<m) return BigInt(0); if(m<256) return div_bz(a,b); BigInt inv=newton_inv(b, n-m+1); return shift(a*inv, -2*(n-m+1)); }
    BigInt operator/(const BigInt& b) const { if(b.v.size()<64) return div_naive(*this,b); if(b.v.size()<256) return div_bz(*this,b); return div_newton(*this,b); }
    BigInt operator%(const BigInt& b) const { return *this - (*this / b) * b; }
    static string to_bin(BigInt a) { string s; while(a.sign) { BigInt q=div_naive(a,BigInt(2)); s+=to_string(a.v.empty()?0:a.v[0]%2); a=q; } return s; }
    static BigInt from_bin(string s) { BigInt a(0), p(1); for(char c:s) { if(c=='1') a=a+p; p=p*BigInt(2); } return a; }
    static BigInt bit_op(BigInt a, BigInt b, int op) { string sa=to_bin(a), sb=to_bin(b), sc; for(size_t i=0;i<max(sa.size(),sb.size());++i) { int ba=i<sa.size()?sa[i]-'0':0, bb=i<sb.size()?sb[i]-'0':0, bc=0; if(op==1) bc=ba&bb; else if(op==2) bc=ba|bb; else bc=ba^bb; sc+=bc?"1":"0"; } return from_bin(sc); }
    BigInt operator&(const BigInt& b) const { return bit_op(*this,b,1); }
    BigInt operator|(const BigInt& b) const { return bit_op(*this,b,2); }
    BigInt operator^(const BigInt& b) const { return bit_op(*this,b,3); }
    BigInt operator~() const { return -(*this) - BigInt(1); }
    BigInt operator<<(long long b) const { BigInt r=*this; while(b>=30) { r=r*BigInt(1<<30); b-=30; } if(b) r=r*BigInt(1<<b); return r; }
    BigInt operator>>(long long b) const { BigInt r=*this; while(b>=30) { r=r/BigInt(1<<30); b-=30; } if(b) r=r/BigInt(1<<b); return r; }
    BigInt& operator+=(const BigInt& b) { return *this = *this + b; }
    BigInt& operator-=(const BigInt& b) { return *this = *this - b; }
    BigInt& operator*=(const BigInt& b) { return *this = *this * b; }
    BigInt& operator/=(const BigInt& b) { return *this = *this / b; }
    BigInt& operator%=(const BigInt& b) { return *this = *this % b; }
    BigInt& operator&=(const BigInt& b) { return *this = *this & b; }
    BigInt& operator|=(const BigInt& b) { return *this = *this | b; }
    BigInt& operator^=(const BigInt& b) { return *this = *this ^ b; }
    BigInt& operator<<=(long long b) { return *this = *this << b; }
    BigInt& operator>>=(long long b) { return *this = *this >> b; }
    BigInt& operator++() { return *this = *this + BigInt(1); }
    BigInt operator++(int) { BigInt t=*this; ++(*this); return t; }
    BigInt& operator--() { return *this = *this - BigInt(1); }
    BigInt operator--(int) { BigInt t=*this; --(*this); return t; }
    friend istream& operator>>(istream& is, BigInt& a) { string s; is>>s; a=BigInt(s); return is; }
    friend ostream& operator<<(ostream& os, const BigInt& a) { if(a.sign==0) return os<<"0"; if(a.sign<0) os<<"-"; os<<a.v.back(); for(int i=(int)a.v.size()-2; i>=0; --i) { string s=to_string(a.v[i]); os<<string(9-s.length(),'0')<<s; } return os; }
};
int main(){
	BigInt a,b;
	cin>>a>>b;
	cout<<a*b;
}
/*

*/

评测结果