dynamic_modint
クラス · modint (static_modint / dynamic_modint)
template <int id>
struct dynamic_modint : internal::modint_common<dynamic_modint<id>>;
概要
実行時に法を設定する modint
計算量
- 四則演算は $O(1)$、累乗と逆元は法を $m$ として $O(\log m)$
構築・破棄
| 名前 | 説明 | 計算量 |
|---|---|---|
(constructor) |
(1) 0を構築する (2) 符号付き整数を現在の法で正規化して構築する (3) 符号なし整数を現在の法で正規化して構築する |
$O(1)$ |
メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
val |
保持している標準剰余を返す （基底 internal::modint_common から継承） |
$O(1)$ |
pow |
n乗を返す （基底 internal::modint_common から継承） |
$O(\log n)$ |
inv |
乗法逆元を返す （基底 internal::modint_common から継承） |
法を $m$ として $O(\log m)$ |
演算子
| 名前 | 説明 | 計算量 |
|---|---|---|
operator++ |
(1) 1を加算する (2) 1を加算する前の値を返す （基底 internal::modint_common から継承） |
$O(1)$ |
operator-- |
(1) 1を減算する (2) 1を減算する前の値を返す （基底 internal::modint_common から継承） |
$O(1)$ |
operator+= |
rhsを加算する （基底 internal::modint_common から継承） |
$O(1)$ |
operator-= |
rhsを減算する （基底 internal::modint_common から継承） |
$O(1)$ |
operator*= |
rhsを乗算する （基底 internal::modint_common から継承） |
$O(1)$ |
operator/= |
rhsで除算する （基底 internal::modint_common から継承） |
素数法では法を $m$ として $O(\log m)$、動的法では $O(\log m)$ |
operator+ |
(1) 自身の値を返す (2) 和を返す （基底 internal::modint_common から継承） |
$O(1)$ |
operator- |
(1) 加法逆元を返す (2) 差を返す （基底 internal::modint_common から継承） |
$O(1)$ |
operator* |
積を返す （基底 internal::modint_common から継承） |
$O(1)$ |
operator/ |
商を返す （基底 internal::modint_common から継承） |
法を $m$ として $O(\log m)$ |
operator== |
等しいか返す （基底 internal::modint_common から継承） |
$O(1)$ |
operator!= |
異なるか返す （基底 internal::modint_common から継承） |
$O(1)$ |
operator>> |
整数を入力して法で正規化する （基底 internal::modint_common から継承） |
$O(1)$ |
operator<< |
標準剰余を出力する （基底 internal::modint_common から継承） |
$O(1)$ |
静的メンバ関数
| 名前 | 説明 | 計算量 |
|---|---|---|
umod |
法を unsigned int で返す | $O(1)$ |
is_prime_mod |
法を素数として扱うか返す | $O(1)$ |
mul |
aとbをBarrett reductionで乗算する | $O(1)$ |
mod |
現在の法を返す | $O(1)$ |
set_mod |
このidの法をmへ設定する | $O(1)$ |
raw |
正規化済みの値vから検査なしで構築する | $O(1)$ |
メンバ型
| 名前 | 説明 | 計算量 |
|---|---|---|
mint |
この型自身 | 型エイリアスで実行時計算量はない |
base |
四則演算を実装する基底型 | 型エイリアスで実行時計算量はない |
_v |
基底型が保持する正規化済みの値 | $O(1)$ で参照可能 |
メンバの詳細
(constructor)
// (1)
dynamic_modint() = default;
// (2)
template <std::integral T>
dynamic_modint(T v);
// (3)
template <std::unsigned_integral T>
dynamic_modint(T v);
(1) 0を構築する
- 計算量: $O(1)$
(2) 符号付き整数を現在の法で正規化して構築する
- 計算量: $O(1)$
(3) 符号なし整数を現在の法で正規化して構築する
- 計算量: $O(1)$
operator++
// (1)
constexpr mint &operator++();
// (2)
constexpr mint operator++(int);
（基底 internal::modint_common から継承）
(1) 1を加算する
- 計算量: $O(1)$
(2) 1を加算する前の値を返す
- 計算量: $O(1)$
operator–
// (1)
constexpr mint &operator--();
// (2)
constexpr mint operator--(int);
（基底 internal::modint_common から継承）
(1) 1を減算する
- 計算量: $O(1)$
(2) 1を減算する前の値を返す
- 計算量: $O(1)$
operator+
// (1)
constexpr mint operator+() const;
// (2)
friend constexpr mint operator+(const mint &lhs, const mint &rhs);
（基底 internal::modint_common から継承）
(1) 自身の値を返す
- 計算量: $O(1)$
(2) 和を返す
- 計算量: $O(1)$
operator-
// (1)
constexpr mint operator-() const;
// (2)
friend constexpr mint operator-(const mint &lhs, const mint &rhs);
（基底 internal::modint_common から継承）
(1) 加法逆元を返す
- 計算量: $O(1)$
(2) 差を返す
- 計算量: $O(1)$
関連項目
modint_common— static_modint と dynamic_modint が共有する公開演算static_modint— コンパイル時に法を固定する modintmodint998— 法998244353のstatic_modintmodint107— 法1000000007のstatic_modintmodint— 既定id -1のdynamic_modint