cplib/math/modint.hpp

• View this file on GitHub
• Last update: 2021-12-25 20:18:09-05:00
• Include: #include "cplib/math/modint.hpp"

Depends on

• cplib/math/binary_exponentiation.hpp

Code

#ifndef CPLIB_modint_HPP
#define CPLIB_modint_HPP

#include <cassert>
#include <cplib/math/binary_exponentiation>
#include <vector>

namespace cplib
{
using namespace std;

template <int M>
class modint
{
    using ll   = long long;
    using mint = modint<M>;
    ll x;

  public:
    static const int           MOD = M;
    inline static vector<mint> inverse{0, 1};

    modint(ll x) : x(x) {}
    modint() : x(0) {}
    modint(mint const &y) : x(y.val()) {}
    explicit  operator ll() const { return val(); }
    explicit  operator int() const { return val(); }
    ll        val(void) const { return mint::val(x); }
    int       mod() const { return MOD; }
    mint      pow(ll n) const { return binpow(val(), n); }
    static ll val(ll x)
    {
        if (x < 0)
            return x + MOD;
        return (x >= MOD ? x % MOD : x);
    }
    mint &operator=(mint const &y)
    {
        x = y.val();
        return *this;
    }
    mint &operator=(ll const &y) { return operator=(mint(y)); }
    mint &operator+=(mint const &y) { return operator=(operator+(y)); }
    mint &operator-=(mint const &y) { return operator=(operator-(y)); }
    mint &operator*=(mint const &y) { return operator=(operator*(y)); }
    mint  operator+(mint const &y) const { return mint::val(val() + y.val()); }
    mint  operator+(ll const &y) const { return operator+(mint(y)); }
    mint  operator-(mint const &y) const { return mint::val(val() - y.val()); }
    mint  operator-(ll const &y) const { return operator-(mint(y)); }
    mint  operator*(mint const &y) const { return mint::val(val() * y.val()); }
    mint  operator*(ll const &y) const { return operator*(mint(y)); }
    mint  operator/(mint const &y) const { return operator*(y.inv()); }
    mint  operator/(ll const &y) const { return operator*(mint::inv(y)); }

    static void precompute_inverses(int len)
    {
        assert(len < 1e8 and len > 0);
        int plen = inverse.size();
        if (len > plen)
        {
            inverse.resize(len);
            for (int i = plen; i < len; ++i)
                inverse[i] = MOD - ll(inverse[MOD % i] * (MOD / i));
        }
    }
    mint        inv(void) const { return mint::inv(val()); }
    static mint inv(ll x)
    {
        assert(x > 0);
        if (x < ll(inverse.size()))
            return inverse[x];
        return binpow(mint(x), MOD - 2);
    }
};
} // namespace cplib

#endif // CPLIB_modint_HPP

#line 1 "cplib/math/modint.hpp"



#include <cassert>
#include <cplib/math/binary_exponentiation>
#include <vector>

namespace cplib
{
using namespace std;

template <int M>
class modint
{
    using ll   = long long;
    using mint = modint<M>;
    ll x;

  public:
    static const int           MOD = M;
    inline static vector<mint> inverse{0, 1};

    modint(ll x) : x(x) {}
    modint() : x(0) {}
    modint(mint const &y) : x(y.val()) {}
    explicit  operator ll() const { return val(); }
    explicit  operator int() const { return val(); }
    ll        val(void) const { return mint::val(x); }
    int       mod() const { return MOD; }
    mint      pow(ll n) const { return binpow(val(), n); }
    static ll val(ll x)
    {
        if (x < 0)
            return x + MOD;
        return (x >= MOD ? x % MOD : x);
    }
    mint &operator=(mint const &y)
    {
        x = y.val();
        return *this;
    }
    mint &operator=(ll const &y) { return operator=(mint(y)); }
    mint &operator+=(mint const &y) { return operator=(operator+(y)); }
    mint &operator-=(mint const &y) { return operator=(operator-(y)); }
    mint &operator*=(mint const &y) { return operator=(operator*(y)); }
    mint  operator+(mint const &y) const { return mint::val(val() + y.val()); }
    mint  operator+(ll const &y) const { return operator+(mint(y)); }
    mint  operator-(mint const &y) const { return mint::val(val() - y.val()); }
    mint  operator-(ll const &y) const { return operator-(mint(y)); }
    mint  operator*(mint const &y) const { return mint::val(val() * y.val()); }
    mint  operator*(ll const &y) const { return operator*(mint(y)); }
    mint  operator/(mint const &y) const { return operator*(y.inv()); }
    mint  operator/(ll const &y) const { return operator*(mint::inv(y)); }

    static void precompute_inverses(int len)
    {
        assert(len < 1e8 and len > 0);
        int plen = inverse.size();
        if (len > plen)
        {
            inverse.resize(len);
            for (int i = plen; i < len; ++i)
                inverse[i] = MOD - ll(inverse[MOD % i] * (MOD / i));
        }
    }
    mint        inv(void) const { return mint::inv(val()); }
    static mint inv(ll x)
    {
        assert(x > 0);
        if (x < ll(inverse.size()))
            return inverse[x];
        return binpow(mint(x), MOD - 2);
    }
};
} // namespace cplib

Back to top page