Dynamic Modint
(Math/dynamic.hpp)

• View this file on GitHub
• Last update: 2023-01-17 01:58:11+09:00
• Include: #include "Math/dynamic.hpp"

Depends on

• Fast Division (Math/fastdiv.hpp)

Verified with

• Verify/LC_multivariate_convolution_cyclic.test.cpp

Code

#pragma once
#include "Math/fastdiv.hpp"


struct Fp{
    using u64=uint64_t;
    int v;
    static int get_mod(){return _getmod();}
    static void set_mod(int _m){bar=FastDiv(_m);}
    Fp inv() const{
        int tmp,a=v,b=get_mod(),x=1,y=0;
        while(b){
            tmp=a/b,a-=tmp*b;
            swap(a,b);
            x-=tmp*y;
            swap(x,y);
        }
        if(x<0){x+=get_mod();}
        return x;
    }
    Fp():v(0){}
    Fp(ll x){
        v=x%get_mod();
        if(v<0)v+=get_mod();
    }
    Fp operator-()const{return Fp()-*this;}
    Fp pow(ll t){
        assert(t>=0);
        Fp res=1,b=*this;
        while(t){
            if(t&1)res*=b;
            b*=b;
            t>>=1;
        }
        return res;
    }
    Fp& operator+=(const Fp& x){
        v+=x.v;
        if(v>=get_mod())v-=get_mod();
        return *this;
    }
    Fp& operator-=(const Fp& x){
        v+=get_mod()-x.v;
        if(v>=get_mod())v-=get_mod();
        return *this;
    }
    Fp& operator*=(const Fp& x){
        v=(u64(v)*x.v)%bar;
        return *this;
    }
    Fp& operator/=(const Fp& x){
        (*this)*=x.inv();
        return *this;
    }
    Fp operator+(const Fp& x)const{return Fp(*this)+=x;}
    Fp operator-(const Fp& x)const{return Fp(*this)-=x;}
    Fp operator*(const Fp& x)const{return Fp(*this)*=x;}
    Fp operator/(const Fp& x)const{return Fp(*this)/=x;}
    bool operator==(const Fp& x)const{return v==x.v;}
    bool operator!=(const Fp& x)const{return v!=x.v;}
private:
    static FastDiv bar;
    static int _getmod(){return bar.get();}
};
FastDiv Fp::bar(998244353);

/**
 * @brief Dynamic Modint
 */

#line 2 "Math/fastdiv.hpp"

struct FastDiv{
    using u64=uint64_t;
    using u128=__uint128_t;
    constexpr FastDiv():m(),s(),x(){}
    constexpr FastDiv(int _m)
        :m(_m),s(__lg(m-1)),x(((u128(1)<<(s+64))+m-1)/m){}
    constexpr int get(){return m;}
    constexpr friend u64 operator/(u64 n,const FastDiv& d){
        return (u128(n)*d.x>>d.s)>>64;
    }
    constexpr friend int operator%(u64 n,const FastDiv& d){
        return n-n/d*d.m;
    }
    constexpr pair<u64,int> divmod(u64 n)const{
        u64 q=n/(*this);
        return {q,n-q*m};
    }
    int m,s; u64 x;
};

/**
 * @brief Fast Division
*/
#line 3 "Math/dynamic.hpp"

struct Fp{
    using u64=uint64_t;
    int v;
    static int get_mod(){return _getmod();}
    static void set_mod(int _m){bar=FastDiv(_m);}
    Fp inv() const{
        int tmp,a=v,b=get_mod(),x=1,y=0;
        while(b){
            tmp=a/b,a-=tmp*b;
            swap(a,b);
            x-=tmp*y;
            swap(x,y);
        }
        if(x<0){x+=get_mod();}
        return x;
    }
    Fp():v(0){}
    Fp(ll x){
        v=x%get_mod();
        if(v<0)v+=get_mod();
    }
    Fp operator-()const{return Fp()-*this;}
    Fp pow(ll t){
        assert(t>=0);
        Fp res=1,b=*this;
        while(t){
            if(t&1)res*=b;
            b*=b;
            t>>=1;
        }
        return res;
    }
    Fp& operator+=(const Fp& x){
        v+=x.v;
        if(v>=get_mod())v-=get_mod();
        return *this;
    }
    Fp& operator-=(const Fp& x){
        v+=get_mod()-x.v;
        if(v>=get_mod())v-=get_mod();
        return *this;
    }
    Fp& operator*=(const Fp& x){
        v=(u64(v)*x.v)%bar;
        return *this;
    }
    Fp& operator/=(const Fp& x){
        (*this)*=x.inv();
        return *this;
    }
    Fp operator+(const Fp& x)const{return Fp(*this)+=x;}
    Fp operator-(const Fp& x)const{return Fp(*this)-=x;}
    Fp operator*(const Fp& x)const{return Fp(*this)*=x;}
    Fp operator/(const Fp& x)const{return Fp(*this)/=x;}
    bool operator==(const Fp& x)const{return v==x.v;}
    bool operator!=(const Fp& x)const{return v!=x.v;}
private:
    static FastDiv bar;
    static int _getmod(){return bar.get();}
};
FastDiv Fp::bar(998244353);

/**
 * @brief Dynamic Modint
 */

Back to top page