動的Modint構造体
(algorithm/Math/ModularArithmetic/dynamic_modint.hpp)

• View this file on GitHub
• Last update: 2025-07-03 00:41:25+09:00
• Include: #include "algorithm/Math/ModularArithmetic/dynamic_modint.hpp"

概要

実行時に法が決まる Modint 構造体．

インスタンスを生成する前に法とする自然数を設定する．

DynamicModint<0>::set_modulus(17);
DynamicModint<1>::set_modulus(23);

DynamicModint<0> a = 28;
DynamicModint<1> b = 28;

cout << a << " " << b << endl;  // 11 5

Depends on

• Modint構造体の基底クラス (algorithm/Math/ModularArithmetic/modint_base.hpp)

Code

#ifndef ALGORITHM_DYNAMIC_MODINT_HPP
#define ALGORITHM_DYNAMIC_MODINT_HPP 1

#include <cassert>
#include <iostream>
#include <utility>

#include "modint_base.hpp"

namespace algorithm {

template <int id>
class DynamicModint : ModintBase {
    static int mod;
    long long val;

    void normalize() {
        if(val < -mod or mod <= val) val %= mod;
        if(val < 0) val += mod;
    }

public:
    DynamicModint() : val(0) {}
    DynamicModint(long long val) : val(val) {
        normalize();
    }

    DynamicModint operator+() const { return DynamicModint(*this); }
    DynamicModint operator-() const {
        if(val == 0) DynamicModint();
        DynamicModint res = *this;
        res.val = mod - res.val;
        return res;
    }
    DynamicModint &operator++() {
        val++;
        if(val == mod) val = 0;
        return *this;
    }
    DynamicModint &operator--() {
        if(val == 0) val = mod;
        val--;
        return *this;
    }
    DynamicModint operator++(int) {
        DynamicModint res = *this;
        ++(*this);
        return res;
    }
    DynamicModint operator--(int) {
        DynamicModint res = *this;
        --(*this);
        return res;
    }
    DynamicModint &operator+=(const DynamicModint &rhs) {
        val += rhs.val;
        if(val >= mod) val -= mod;
        return *this;
    }
    DynamicModint &operator-=(const DynamicModint &rhs) {
        val -= rhs.val;
        if(val < 0) val += mod;
        return *this;
    }
    DynamicModint &operator*=(const DynamicModint &rhs) {
        val = val * rhs.val % mod;
        return *this;
    }
    DynamicModint &operator/=(const DynamicModint &rhs) { return *this *= rhs.inv(); }

    friend bool operator==(const DynamicModint &lhs, const DynamicModint &rhs) { return lhs.val == rhs.val; }
    friend DynamicModint operator+(const DynamicModint &lhs, const DynamicModint &rhs) { return DynamicModint(lhs) += rhs; }
    friend DynamicModint operator-(const DynamicModint &lhs, const DynamicModint &rhs) { return DynamicModint(lhs) -= rhs; }
    friend DynamicModint operator*(const DynamicModint &lhs, const DynamicModint &rhs) { return DynamicModint(lhs) *= rhs; }
    friend DynamicModint operator/(const DynamicModint &lhs, const DynamicModint &rhs) { return DynamicModint(lhs) /= rhs; }
    friend std::istream &operator>>(std::istream &is, DynamicModint &rhs) {
        is >> rhs.val;
        rhs.normalize();
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const DynamicModint &rhs) { return os << rhs.val; }

    static constexpr int get_id() { return id; }
    static int modulus() { return mod; }
    static void set_modulus(int mod) {
        assert(mod >= 1);
        DynamicModint::mod = mod;
    }
    long long value() const { return val; }
    DynamicModint inv() const {
        long long a = mod, b = val, u = 0, v = 1;
        while(b != 0) {
            long long t = a / b;
            a -= b * t, u -= v * t;
            std::swap(a, b), std::swap(u, v);
        }
        return DynamicModint(u);
    }
    DynamicModint pow(long long k) const {
        if(k < 0) return inv().pow(-k);
        DynamicModint res = 1, mul = *this;
        while(k > 0) {
            if(k & 1LL) res *= mul;
            mul *= mul;
            k >>= 1;
        }
        return res;
    }

    friend DynamicModint mod_inv(const DynamicModint &a) { return a.inv(); }
    friend DynamicModint mod_pow(const DynamicModint &a, long long k) { return a.pow(k); }
};

template <int id>
int DynamicModint<id>::mod = 1'000'000'007;

}  // namespace algorithm

#endif

#line 1 "algorithm/Math/ModularArithmetic/dynamic_modint.hpp"



#include <cassert>
#include <iostream>
#include <utility>

#line 1 "algorithm/Math/ModularArithmetic/modint_base.hpp"



#include <type_traits>

namespace algorithm {

class ModintBase {};

template <class T>
using is_modint = std::is_base_of<ModintBase, T>;

template <class T>
inline constexpr bool is_modint_v = is_modint<T>::value;

}  // namespace algorithm


#line 9 "algorithm/Math/ModularArithmetic/dynamic_modint.hpp"

namespace algorithm {

template <int id>
class DynamicModint : ModintBase {
    static int mod;
    long long val;

    void normalize() {
        if(val < -mod or mod <= val) val %= mod;
        if(val < 0) val += mod;
    }

public:
    DynamicModint() : val(0) {}
    DynamicModint(long long val) : val(val) {
        normalize();
    }

    DynamicModint operator+() const { return DynamicModint(*this); }
    DynamicModint operator-() const {
        if(val == 0) DynamicModint();
        DynamicModint res = *this;
        res.val = mod - res.val;
        return res;
    }
    DynamicModint &operator++() {
        val++;
        if(val == mod) val = 0;
        return *this;
    }
    DynamicModint &operator--() {
        if(val == 0) val = mod;
        val--;
        return *this;
    }
    DynamicModint operator++(int) {
        DynamicModint res = *this;
        ++(*this);
        return res;
    }
    DynamicModint operator--(int) {
        DynamicModint res = *this;
        --(*this);
        return res;
    }
    DynamicModint &operator+=(const DynamicModint &rhs) {
        val += rhs.val;
        if(val >= mod) val -= mod;
        return *this;
    }
    DynamicModint &operator-=(const DynamicModint &rhs) {
        val -= rhs.val;
        if(val < 0) val += mod;
        return *this;
    }
    DynamicModint &operator*=(const DynamicModint &rhs) {
        val = val * rhs.val % mod;
        return *this;
    }
    DynamicModint &operator/=(const DynamicModint &rhs) { return *this *= rhs.inv(); }

    friend bool operator==(const DynamicModint &lhs, const DynamicModint &rhs) { return lhs.val == rhs.val; }
    friend DynamicModint operator+(const DynamicModint &lhs, const DynamicModint &rhs) { return DynamicModint(lhs) += rhs; }
    friend DynamicModint operator-(const DynamicModint &lhs, const DynamicModint &rhs) { return DynamicModint(lhs) -= rhs; }
    friend DynamicModint operator*(const DynamicModint &lhs, const DynamicModint &rhs) { return DynamicModint(lhs) *= rhs; }
    friend DynamicModint operator/(const DynamicModint &lhs, const DynamicModint &rhs) { return DynamicModint(lhs) /= rhs; }
    friend std::istream &operator>>(std::istream &is, DynamicModint &rhs) {
        is >> rhs.val;
        rhs.normalize();
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const DynamicModint &rhs) { return os << rhs.val; }

    static constexpr int get_id() { return id; }
    static int modulus() { return mod; }
    static void set_modulus(int mod) {
        assert(mod >= 1);
        DynamicModint::mod = mod;
    }
    long long value() const { return val; }
    DynamicModint inv() const {
        long long a = mod, b = val, u = 0, v = 1;
        while(b != 0) {
            long long t = a / b;
            a -= b * t, u -= v * t;
            std::swap(a, b), std::swap(u, v);
        }
        return DynamicModint(u);
    }
    DynamicModint pow(long long k) const {
        if(k < 0) return inv().pow(-k);
        DynamicModint res = 1, mul = *this;
        while(k > 0) {
            if(k & 1LL) res *= mul;
            mul *= mul;
            k >>= 1;
        }
        return res;
    }

    friend DynamicModint mod_inv(const DynamicModint &a) { return a.inv(); }
    friend DynamicModint mod_pow(const DynamicModint &a, long long k) { return a.pow(k); }
};

template <int id>
int DynamicModint<id>::mod = 1'000'000'007;

}  // namespace algorithm

Back to top page