题解：P1001 A+B Problem

K8He · 2025-05-10 12:05:13 · 题解

如果是 A*B Problem，我们可以轻松将其转化成多项式乘法问题。

此题容易注意到使用经典结论，先使用多项式 exp 一步将加法转换成乘法再使用多项式 ln 得到答案。

有一点细节 WA 了几发：

• 多项式 ln 会忽略常数项，所以应当先对 a, b 乘 10。
• 乘 10 以后是 11 位数不是 10 位数。
• 负数的情况可以先全都加上 10^9，最后对答案减去 2\times 10^9。

然后就可以愉快的通过了！

代码（可能有人问 namespace POLY 是什么吧，是史哦！）：

#include <bits/stdc++.h>
#define _for(i, a, b) for (int i = a; i <= b; ++i)
#define for_(i, a, b) for (int i = a; i >= b; --i)
#define far(i, vec) for (auto i : vec)
#define bdmd int mid = (l + r) >> 1
typedef long double ldb;
typedef long long ll;
typedef double db;
typedef std::pair <int, int> pii;
typedef std::pair <ll, ll> pll;
const int N = 1e5 + 10, P = 998244353;
namespace IO {
    int rnt () {
        int x = 0, w = 1; char c = getchar ();
        while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
        while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
        return x * w;
    }
}
namespace POLY {
    const int N=3e5+10,P=998244353,g=3,invg=332748118;int rev[N],omega[2][N];
    std::mt19937 rnd (std::chrono::system_clock::now ().time_since_epoch ().count ());
    template<typename T1,typename T2>inline T1 add(T1 a,T2 b){return(a+=b)>=POLY::P?a-POLY::P:a;}template<typename T1,typename T2>inline void addi(T1&a,T2 b){(a+=b)>=POLY::P?a-=POLY::P:a;return;}template<typename T1,typename...Args>inline T1 add(T1 a,Args...b){return add(a,add(b...));}template<typename T1,typename...Args>inline void addi(T1&a,Args...b){addi(a,add(b...));return;}
    template<typename T1,typename T2>inline T1 sub(T1 a,T2 b){return(a-=b)<0?a+POLY::P:a;}template<typename T1,typename T2>inline void subi(T1&a,T2 b){(a-=b)<0?a+=POLY::P:a;return;}template<typename T1,typename...Args>inline T1 sub(T1 a,Args...b){return sub(a,add(b...));}template<typename T1,typename...Args>inline void subi(T1&a,Args...b){subi(a,add(b...));return;}
    template<typename T1,typename T2>inline T1 mul(T1 a,T2 b){return(1ll*a*b)%POLY::P;}template<typename T1,typename T2>inline void muli(T1&a,T2 b){a=mul(a,b);return;}template<typename T1,typename...Args>T1 inline mul(T1 a,Args...b){return mul(a,mul(b...));}template<typename T1,typename...Args>inline void muli(T1&a,Args...b){muli(a,mul(b...));return;}
    template<typename T1,typename T2>inline T1 FastPow(T1 a,T2 b){T1 ans=1;while(b){if(b&1)muli(ans,a);muli(a,a),b>>=1;}return ans;}template<typename T>inline T Inv(T a){return FastPow(a,POLY::P-2);}
    inline int PreWork(const int &n){int lim=1,l=0;while(lim<=n)lim<<=1,++l;_for(i,0,lim)rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));omega[0][0]=omega[1][0]=1;omega[0][1]=FastPow(g,(POLY::P-1)/lim);omega[1][1]=FastPow(invg,(POLY::P-1)/lim);_for(i,2,lim)omega[0][i]=mul(omega[0][i-1],omega[0][1]),omega[1][i]=mul(omega[1][i-1],omega[1][1]);return lim;}
    namespace Cipolla{int _i_;class Complex{public:int real,imag;Complex()=default;Complex(int _real,int _imag):real(_real),imag(_imag){}inline void operator*=(Complex b){int tmp1=add(mul(real,b.real),mul(imag,b.imag,_i_));int tmp2=add(mul(real,b.imag),mul(imag,b.real));real=tmp1,imag=tmp2;return;}};inline int FastPow(Complex a,int b){Complex ans(1,0);while(b){if(b&1)ans*=a;a*=a,b>>=1;}return ans.real;}inline int Cipolla(int n){if (!n)return 0;if (POLY::FastPow(n,(POLY::P-1)>>1)==POLY::P-1)return -1;int a;while(a){a=rnd()%POLY::P,_i_=sub(mul(a,a),n);if(POLY::FastPow(_i_,(POLY::P-1)>>1)==POLY::P-1)break;}return FastPow(Complex(a,1),(POLY::P+1)>>1);}};
    template<typename T = int> class Poly {
    private:std::vector<T>A;
    public:
        Poly()=default;Poly(int len){A.resize(len);return;}Poly(std::vector<T> _A):A(_A){}Poly(typename std::vector<T>::iterator bg,typename std::vector<T>::iterator ed){A.assign(bg,ed);return;}Poly(typename std::vector<T>::iterator bg,int len){A.assign(bg,bg+len);return;}
        inline T& operator[](const int& x){return A[x];}inline T operator[](const int& x)const{return A[x];}
        inline int deg()const{return A.size()-1;}inline int len()const{return A.size();}inline Poly Resize(int len){A.resize(len);return(*this);}
        inline typename std::vector<T>::iterator begin(){return A.begin();}inline typename std::vector<T>::iterator end(){return A.end();}inline T* data(){return A.data();}
        inline void Cover(typename std::vector<T>::iterator bg,typename std::vector<T>::iterator ed){A.assign(bg,ed);return;}inline void Cover(typename std::vector<T>::iterator bg,int len){A.assign(bg,bg+len);return;}
        inline Poly Slice(int n){return n<=0?Poly(0):(n<len()?Poly(begin(),begin()+n+1):Poly(*this).Resize(n+1));}inline void Clear(){std::vector<T>().swap(A);return;}
        inline void NTT(int lim,bool type){Resize(lim);_for(i,0,lim-1)if(i<rev[i])std::swap(A[i],A[rev[i]]);for(int mid=1,t=lim>>1;mid<lim;mid<<=1,t>>=1){for(int R=mid<<1,j=0;j<lim;j+=R){_for(k,0,mid-1){T x=A[j+k],y=mul(omega[type][t*k],A[j+mid+k]);A[j+k]=add(x,y),A[j+mid+k]=sub(x,y);}}}if(type==1){T inv_lim=FastPow(lim,POLY::P-2);_for(i,0,lim-1)A[i]=mul(A[i],inv_lim);}return;}
        friend inline Poly operator+(Poly F,Poly G){F.Resize(std::max(F.len(),G.len()));_for(i,0,G.deg())addi(F[i],G[i]);return F;}inline Poly&operator+=(Poly G){Resize(std::max(len(),G.len()));_for(i,0,G.deg())addi(A[i],G[i]);return(*this);}
        friend inline Poly operator+(Poly F,T x){addi(F[0],x);return F;}friend inline Poly operator+(T x,Poly F){addi(F[0],x);return F;}inline Poly&operator+=(T x){addi(A[0],x);return(*this);}
        friend inline Poly operator-(Poly F,Poly G){F.Resize(std::max(F.len(),G.len()));_for(i,0,G.deg())subi(F[i],G[i]);return F;}inline Poly&operator-=(Poly G){Resize(std::max(len(),G.len()));_for(i,0,G.deg())subi(A[i],G[i]);return(*this);}
        friend inline Poly operator-(Poly F,T x){subi(F[0],x);return F;}friend inline Poly operator-(T x,Poly F){subi(F[0],x);return F;}inline Poly&operator-=(T x){subi(A[0],x);return(*this);}
        friend inline Poly operator*(Poly F,Poly G){int lim=PreWork(F.deg()+G.deg());F.NTT(lim,0),G.NTT(lim,0);_for(i,0,lim-1)muli(F[i],G[i]);F.NTT(lim,1);return F;}inline Poly&operator*=(Poly G){int lim=PreWork(deg()+G.deg());NTT(lim,0),G.NTT(lim,0);_for(i,0,lim-1)muli(A[i],G[i]);NTT(lim,1);return(*this);}
        friend inline Poly operator*(Poly F,T x){_for(i,0,F.deg())muli(F[i],x);return F;}friend inline Poly operator*(T x,Poly F){_for(i,0,F.deg())muli(F[i],x);return F;}inline Poly&operator*=(T x){_for(i,0,deg())muli(A[i],x);return(*this);}
        friend inline Poly operator/(Poly F,T x){x=POLY::Inv(x);return F*x;}friend inline Poly operator/(T x,Poly F){x=POLY::Inv(x);return F*x;}inline Poly&operator/=(T x){x=POLY::Inv(x);(*this)*=x;return(*this);}
        friend inline Poly operator<<(Poly F,int x){F.Resize(F.len()+x),memmove(F.data()+x,F.data(),4*(F.len()-x)),memset(F.data(),0,4*x);return F;}inline Poly&operator<<=(int x){Resize(len()+x),memmove(data()+x,data(),4*(len()-x)),memset(data(),0,4*x);return(*this);}
        friend inline Poly operator>>(Poly F,int x){if(x>=F.len())F.Clear();else memmove(F.data(),F.data()+x,4*(F.len()-x)),F.Resize(F.len()-x);return F;}inline Poly& operator>>=(int x){return x>=len()?(Clear(),*this):(memmove(data(),data()+x,4*(len()-x)),Resize(len()-x),*this);}
        inline Poly Inv(){Poly G(1);if(A.empty())return G;G[0]=POLY::Inv(A[0]);Poly t[2];for(int l=2;l<(len()<<1);l<<=1){t[0].Cover(A.begin(),std::min(l,len()));t[1]=G,t[1].Resize(std::min(l,len()));int lim=PreWork(t[0].deg()+t[1].deg()+1);t[0].NTT(lim,0),t[1].NTT(lim,0),G.Resize(lim);_for(i,0,lim-1)G[i]=mul(sub(2,mul(t[0][i],t[1][i])),t[1][i]);G.NTT(lim,1),G.Resize(l);}G.Resize(len());return G;}
        inline Poly Sqrt(){Poly G(1);G[0]=Cipolla::Cipolla(A[0]),G[0]=std::min(G[0],POLY::P-G[0]);T inv2=POLY::Inv(2);Poly t[2];for(int l=2;l<(len()<<1);l<<=1){t[1].Cover(A.begin(),std::min(l,len()));G.Resize(l),t[0]=G.Inv()*t[1];_for(i,0,l-1)G[i]=mul(t[0][i]+G[i],inv2);}G.Resize(len());return G;}
        inline Poly Differential(){Poly G(len()-1);_for(i,0,deg()-1)G[i]=mul(A[i+1],i+1);return G;}inline void iDifferential(){_for(i,0,deg()-1)A[i]=mul(A[i+1],i+1);A.resize(len()-1);return;}
        inline Poly Integral(){Poly G(len());for_(i,deg(),1)G[i]=mul(A[i-1],POLY::Inv(i));return G;}inline void iIntegral(){A.resize(len());for_(i,deg(),1)A[i]=mul(A[i-1],POLY::Inv(i));A[0]=0;return;}
        inline Poly Ln(){Poly G=(Differential()*Inv()).Integral();G.Resize(len());return G;}
        inline Poly Exp(){Poly G(1),H;G[0]=1;T inv2=POLY::Inv(2);for(int l=2;l<(len()<<1);l<<=1)G.Resize(l),H.Cover(A.begin(),std::min(l,len())),H-=G.Ln(),++H[0],G*=H;G.Resize(len());return G;}
        inline Poly Power(int k){if(A[0]!=0)return((((*this)*FastPow(A[0],P-2)).Ln())*k).Exp()*FastPow(A[0],k);else _for(i,0,deg())if(A[i]!=0)return((*this)>>i).Power(k)<<(i*k);return Poly(len());}
        inline Poly Power(pii k){if(A[0]!=0)return((((*this)*FastPow(A[0],P-2)).Ln())*k.second).Exp()*FastPow(A[0],k.first);else _for(i,0,deg())if(A[i]!=0)return(1ll*i*k.first)>len()?Poly(len()):((*this)>>i).Power(k)<<(i*k.first);return Poly(len());};
    };
} using poly = POLY::Poly<int>;
namespace SOLVE {
    using namespace IO;
    ll a, b, ans;
    poly A, B, C;
    void In () {
        a = rnt (), b = rnt ();
        return;
    }
    void Solve () {
        a += 1000'000'000ll;
        b += 1000'000'000ll;
        a *= 10, b *= 10;
        A.Resize (11), B.Resize (11);
        _for (i, 0, 10) {
            A[i] = a % 10, a /= 10;
            B[i] = b % 10, b /= 10;
        }
        A = A.Exp (), B = B.Exp ();
        C = A * B;
        C = C.Ln ();
        ll t = 1;
        _for (i, 0, std::min (10, C.deg ()))
            ans = ans + t * C[i], t *= 10;
        ans /= 10;
        ans -= 2000'000'000ll;
        return;
    }
    void Out () {
        printf ("%lld\n", ans);
        return;
    }
}
int main () {
    SOLVE::In ();
    SOLVE::Solve ();
    SOLVE::Out ();
    return 0;
} /*

*/