任意の法の modint

math/modint.hpp · GitHub で見る

共通ページ

#include "lib/math/modint.hpp"
#include <cassert>

int main() {
	using Mint = StaticModint<1000000007>;
	Mint a = -2;
	assert((a * a).val() == 4);
	DynamicModint<>::set_mod(12);
	DynamicModint<> b = 5;
	assert(b.inv().val() == 5);
}

StaticModint<Mod> はコンパイル時に法を固定し、DynamicModint<Id = 0> は実行時に法を設定します。法は std::uint32_t の正の値で、素数・合成数の両方に対応します。動的版の初期の法は 998244353 です。Id が異なる型は法を独立に保持します。

操作	内容・返り値
Mint() / Mint(x)	0／整数を法で正規化して構築。符号付き・符号なし 128 bit 整数まで対応
Mint::mod()	法を std::uint32_t で返す
DynamicModint<Id>::set_mod(m)	その Id の法を変更。m >= 1
Mint::raw(x)	0 <= x < mod() の std::uint32_t を正規化せず格納
a.val()	0 <= value < mod() の std::uint32_t を返す
+a / -a / a+b / a-b / a*b / a/b	同じ型の modint の演算。整数との混合演算も可能
+= / -= / *= / /=	演算して自身への参照を返す
++a / --a / a++ / a--	1 の加算・減算
== / !=	正規化された値を比較
a.pow(n)	非負の std::int64_t 指数による累乗。同じ modint 型を返す。0 の 0 乗は 1 を法で正規化した値
a.inv()	逆元を同じ型で返す。法と互いに素でないとき std::domain_error
>> / <<	std::int64_t の入力／正規化された値の出力

割り算は除数の逆元を掛けます。法 1 のときは全ての値が 0 で、逆元も 0 とします。負の指数は std::invalid_argument です。動的版は、値を利用している間に法を変更しないでください。法の設定変更を別スレッドと同時に行うことはできません。

StaticModint の構築・加減乗算・比較・累乗は定数式でも利用できます。既定の高速な mint は modint998244353 を使ってください。StaticModint は静的 modint を受け取る畳み込みなどにも渡せます。動的版は、法をコンパイル時定数として要求する API には渡せません。

法を \(m\) とすると、構築・加減乗算・比較・値の取得・法の設定は \(O(1)\)、逆元・除算は \(O(\log m)\)、累乗は \(O(\log n)\) 時間です。指数 0 は定数時間です。各値の空間は \(O(1)\) です。

依存ライブラリ

• 32 bit Barrett 演算
• 一次合同式
• 剰余累乗・逆元

コード

#ifndef MODINT_HPP
#define MODINT_HPP

#include "modular_arithmetic.hpp"
#include <cassert>
#include <istream>
#include <ostream>
#include <type_traits>

namespace modint_detail {
template <std::uint32_t Mod> struct StaticModulus {
	static_assert(Mod > 0);
	static constexpr std::uint32_t mod() { return Mod; }
	static constexpr std::uint32_t mul(std::uint32_t a, std::uint32_t b) { return std::uint64_t(a) * b % Mod; }
};
template <int Id> struct DynamicModulus {
	static inline Barrett32 reducer{998244353};
	static std::uint32_t mod() { return reducer.mod; }
	static std::uint32_t mul(std::uint32_t a, std::uint32_t b) { return reducer.mul(a, b); }
};
template <class Policy> class [[gnu::warn_unused]] Modint {
	std::uint32_t value_ = 0;
public:
	constexpr Modint() = default;
	template <class I, std::enable_if_t<std::is_integral_v<I> || std::is_same_v<I, __int128_t> || std::is_same_v<I, __uint128_t>, int> = 0>
	constexpr Modint(I x) {
		if constexpr (std::is_signed_v<I> || std::is_same_v<I, __int128_t>) {
			auto r = __int128_t(x) % mod();
			value_ = std::uint32_t(r < 0 ? r + mod() : r);
		} else value_ = std::uint32_t(__uint128_t(x) % mod());
	}
	[[nodiscard]] static constexpr std::uint32_t mod() { return Policy::mod(); }
	static void set_mod(std::uint32_t m) requires requires { Policy::reducer; } { Policy::reducer = Barrett32(m); }
	[[nodiscard]] static constexpr Modint raw(std::uint32_t x) { assert(x < mod()); Modint result; result.value_ = x; return result; }
	[[nodiscard]] constexpr std::uint32_t val() const { return value_; }
	constexpr Modint &operator+=(Modint x) {
		std::uint64_t sum = std::uint64_t(value_) + x.value_;
		value_ = std::uint32_t(sum >= mod() ? sum - mod() : sum);
		return *this;
	}
	constexpr Modint &operator-=(Modint x) { value_ = value_ >= x.value_ ? value_ - x.value_ : std::uint32_t(std::uint64_t(value_) + mod() - x.value_); return *this; }
	constexpr Modint &operator*=(Modint x) { value_ = Policy::mul(value_, x.value_); return *this; }
	Modint &operator/=(Modint x) { return *this *= x.inv(); }
	[[nodiscard]] constexpr Modint operator+() const { return *this; }
	[[nodiscard]] constexpr Modint operator-() const { return raw(value_ ? mod() - value_ : 0); }
	constexpr Modint &operator++() { return *this += 1; }
	constexpr Modint &operator--() { return *this -= 1; }
	constexpr Modint operator++(int) { auto old = *this; ++*this; return old; }
	constexpr Modint operator--(int) { auto old = *this; --*this; return old; }
	[[nodiscard]] friend constexpr Modint operator+(Modint a, Modint b) { return a += b; }
	[[nodiscard]] friend constexpr Modint operator-(Modint a, Modint b) { return a -= b; }
	[[nodiscard]] friend constexpr Modint operator*(Modint a, Modint b) { return a *= b; }
	[[nodiscard]] friend Modint operator/(Modint a, Modint b) { return a /= b; }
	[[nodiscard]] friend constexpr bool operator==(Modint, Modint) = default;
	[[nodiscard]] constexpr Modint pow(std::int64_t n) const {
		if (n < 0) throw std::invalid_argument("modint exponent");
		Modint result(1), x = *this;
		for (; n; n >>= 1, x *= x) if (n & 1) result *= x;
		return result;
	}
	[[nodiscard]] Modint inv() const { return raw(std::uint32_t(inv_mod(value_, mod()))); }
	friend std::istream &operator>>(std::istream &in, Modint &x) { std::int64_t value; if (in >> value) x = value; return in; }
	friend std::ostream &operator<<(std::ostream &out, Modint x) { return out << x.val(); }
};
}

template <std::uint32_t Mod> using StaticModint = modint_detail::Modint<modint_detail::StaticModulus<Mod>>;
template <int Id = 0> using DynamicModint = modint_detail::Modint<modint_detail::DynamicModulus<Id>>;

#endif

Back to top page