modint
(math/modint.hpp)

• View this file on GitHub
• Last update: 2024-06-20 15:39:33+09:00
• Include: #include "math/modint.hpp"

なんかうまくやってくれます。生成AIが書いてくれました。

Depends on

• math/external_gcd.hpp

Required by

• formal-power-series/fiduccia.hpp
• Formal Power Series (形式的べき級数) (formal-power-series/formal-power-series.hpp)
• formal-power-series/fps998.hpp
• sparse-fps (formal-power-series/sparse-fps.hpp)
• test/verify/atcoder-tdpc-s.cpp
• test/verify/fps/yosupo-inv-of-formal-power-series-naive-test.cpp
• test/verify/fps/yosupo-inv-of-formal-power-series-naive-test.cpp
• test/verify/fps/yosupo-kth-term-of-linearly-recurrent-sequence-test.cpp
• test/verify/fps/yosupo-kth-term-of-linearly-recurrent-sequence-test.cpp

Verified with

• test/unittest/unittest-multiple-divisor-moebius-transform.test.cpp
• test/verify/convolution/yosupo-and-convolution.test.cpp
• test/verify/convolution/yosupo-gcd-convolution.test.cpp
• test/verify/convolution/yosupo-lcm-convolution.test.cpp
• test/verify/fps/yosupo-division-of-polynomials.test.cpp
• test/verify/fps/yosupo-division-of-polynomials.test.cpp
• test/verify/fps/yosupo-exp-of-formal-power-series.test.cpp
• test/verify/fps/yosupo-exp-of-formal-power-series.test.cpp
• test/verify/fps/yosupo-inv-of-formal-power-series-fast2.test.cpp
• test/verify/fps/yosupo-inv-of-formal-power-series-fast2.test.cpp
• test/verify/fps/yosupo-inv-of-formal-power-series-sparse.test.cpp
• test/verify/fps/yosupo-inv-of-formal-power-series-sparse.test.cpp
• test/verify/fps/yosupo-log-of-formal-power-series.test.cpp
• test/verify/fps/yosupo-log-of-formal-power-series.test.cpp
• test/verify/math/matrix/yosupo-inverse-of-matrix.test.cpp
• test/verify/math/matrix/yosupo-matrix-product.test.cpp
• test/verify/math/matrix/yosupo-pow-of-matrix.test.cpp
• test/verify/math/matrix/yosupo-rank-of-matrix.test.cpp
• test/verify/yosupo-deque-operate-all-composite.test.cpp
• test/verify/yosupo-queue-operate-all-composite.test.cpp
• test/verify/yuki-372-itsautomatic.test.cpp

Code

#ifndef HARUILIB_MATH_MODINT_HPP
#define HARUILIB_MATH_MODINT_HPP

#include "math/external_gcd.hpp"

template<int MOD>
struct static_modint {
    int value;

    constexpr static_modint() : value(0) {}

    constexpr static_modint(long long v) {
        value = int(((v % MOD) + MOD) % MOD);
    }

    constexpr static_modint& operator+=(const static_modint& other) {
        if ((value += other.value) >= MOD) value -= MOD;
        return *this;
    }

    constexpr static_modint& operator-=(const static_modint& other) {
        if ((value -= other.value) < 0) value += MOD;
        return *this;
    }

    constexpr static_modint& operator*=(const static_modint& other) {
        value = int((long long)value * other.value % MOD);
        return *this;
    }

    constexpr static_modint operator+(const static_modint& other) const {
        return static_modint(*this) += other;
    }

    constexpr static_modint operator-(const static_modint& other) const {
        return static_modint(*this) -= other;
    }

    constexpr static_modint operator*(const static_modint& other) const {
        return static_modint(*this) *= other;
    }

    constexpr static_modint pow(long long exp) const {
        static_modint base = *this, res = 1;
        while (exp > 0) {
            if (exp & 1) res *= base;
            base *= base;
            exp >>= 1;
        }
        return res;
    }

    constexpr static_modint inv() const {
        //return pow(MOD - 2);
        int g,x,y;
        tie(g,x,y) = extendedGCD(value, MOD);
        assert(g==1);
        if (x < 0) {
            x += MOD;
        }
        //cerr << g << " " << x << " " << y << " " << value << endl;
        //assert((((long)x*value)%MOD + MOD)%MOD == 1);
        return x;
    }

    constexpr static_modint& operator/=(const static_modint& other) {
        return *this *= other.inv();
    }

    constexpr static_modint operator/(const static_modint& other) const {
        return static_modint(*this) /= other;
    }

    constexpr bool operator!=(const static_modint& other) const {
        return val() != other.val();
    }

    constexpr bool operator==(const static_modint& other) const {
        return val() == other.val();
    }

    int val() const {
      return this->value;
    }

    friend std::ostream& operator<<(std::ostream& os, const static_modint& mi) {
        return os << mi.value;
    }

    friend std::istream& operator>>(std::istream& is, static_modint& mi) {
        long long x;
        is >> x;
        mi = static_modint(x);
        return is;
    }
};

template <int mod>
using modint = static_modint<mod>;
using modint998244353  = modint<998244353>;
using modint1000000007 = modint<1000000007>;

#endif // HARUILIB_MATH_MODINT_HPP

#line 1 "math/modint.hpp"



#line 1 "math/external_gcd.hpp"



#include <tuple>

// g,x,y
template<typename T>
constexpr std::tuple<T, T, T> extendedGCD(T a, T b) {
    T x0 = 1, y0 = 0, x1 = 0, y1 = 1;
    while (b != 0) {
        T q = a / b;
        T r = a % b;
        a = b;
        b = r;
        
        T xTemp = x0 - q * x1;
        x0 = x1;
        x1 = xTemp;
        
        T yTemp = y0 - q * y1;
        y0 = y1;
        y1 = yTemp;
    }
    return {a, x0, y0};
}

#line 5 "math/modint.hpp"

template<int MOD>
struct static_modint {
    int value;

    constexpr static_modint() : value(0) {}

    constexpr static_modint(long long v) {
        value = int(((v % MOD) + MOD) % MOD);
    }

    constexpr static_modint& operator+=(const static_modint& other) {
        if ((value += other.value) >= MOD) value -= MOD;
        return *this;
    }

    constexpr static_modint& operator-=(const static_modint& other) {
        if ((value -= other.value) < 0) value += MOD;
        return *this;
    }

    constexpr static_modint& operator*=(const static_modint& other) {
        value = int((long long)value * other.value % MOD);
        return *this;
    }

    constexpr static_modint operator+(const static_modint& other) const {
        return static_modint(*this) += other;
    }

    constexpr static_modint operator-(const static_modint& other) const {
        return static_modint(*this) -= other;
    }

    constexpr static_modint operator*(const static_modint& other) const {
        return static_modint(*this) *= other;
    }

    constexpr static_modint pow(long long exp) const {
        static_modint base = *this, res = 1;
        while (exp > 0) {
            if (exp & 1) res *= base;
            base *= base;
            exp >>= 1;
        }
        return res;
    }

    constexpr static_modint inv() const {
        //return pow(MOD - 2);
        int g,x,y;
        tie(g,x,y) = extendedGCD(value, MOD);
        assert(g==1);
        if (x < 0) {
            x += MOD;
        }
        //cerr << g << " " << x << " " << y << " " << value << endl;
        //assert((((long)x*value)%MOD + MOD)%MOD == 1);
        return x;
    }

    constexpr static_modint& operator/=(const static_modint& other) {
        return *this *= other.inv();
    }

    constexpr static_modint operator/(const static_modint& other) const {
        return static_modint(*this) /= other;
    }

    constexpr bool operator!=(const static_modint& other) const {
        return val() != other.val();
    }

    constexpr bool operator==(const static_modint& other) const {
        return val() == other.val();
    }

    int val() const {
      return this->value;
    }

    friend std::ostream& operator<<(std::ostream& os, const static_modint& mi) {
        return os << mi.value;
    }

    friend std::istream& operator>>(std::istream& is, static_modint& mi) {
        long long x;
        is >> x;
        mi = static_modint(x);
        return is;
    }
};

template <int mod>
using modint = static_modint<mod>;
using modint998244353  = modint<998244353>;
using modint1000000007 = modint<1000000007>;

Back to top page