自動でmodを取る構造体です。AC Libraryはmodintを使わなくとも全アルゴリズムが使えるように整備しているので、必ずしもこのファイルの内容を把握する必要はありません�。
多くの問題では modint998244353
, modint1000000007
, modint
のどれかを使えば十分で、以下のように使えます。
#include <atcoder/modint>
#include <iostream>
using namespace std;
using namespace atcoder;
using mint = modint998244353;
// or: typedef modint998244353 mint;
int main() {
// print sum of array (mod 998244353)
int n;
cin >> n;
mint sum = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
sum += x;
}
cout << sum.val() << endl;
}
modがfixedでない場合は、modint
を使用し以下のように書けます。
#include <atcoder/modint>
#include <iostream>
using namespace std;
using namespace atcoder;
using mint = modint;
// or: typedef modint mint;
int main() {
// print sum of array (input mod)
int n, mod;
cin >> n >> mod;
mint::set_mod(mod);
mint sum = 0;
for (int i = 0; i < n; i++) {
int x;
cin >> x;
sum += x;
}
cout << sum.val() << endl;
}
以下の関数らは、set_mod
を除き
(1) modint x()
(2) modint x<T>(T y)
- (1) modintのデフォルトコンストラクタです。$0$ が格納されます。
- (2) 整数型
T
(int, char, ull, bool, ...
) に対するコンストラクタです。y
のmodを取ってmodintに格納します。
void modint::set_mod(int m)
modを設定します。最初に呼んでください。
@{keyword.constraints}
$1 \leq m \leq 2 \times 10^9 + 1000$
@{keyword.complexity}
$O(1)$
int modint::mod()
modを返します。
int x.val();
x
に格納されている値を返します。
-modint;
modint++;
modint--;
++modint;
--modint;
modint + modint;
modint - modint;
modint * modint;
modint / modint;
modint += modint;
modint -= modint;
modint *= modint;
modint /= modint;
modint == modint;
modint != modint;
が動きます。
modint x = 10;
1 + x;
も(modint(1) + x
と自動で解釈されるので)動きます。
modint::set_mod(11);
modint y = 10;
int z = 1234;
y * z;
もy * modint(z)
と解釈され、動きます。
@{keyword.constraints}
a / b
(ora /= b
)を行なう時、gcd(b.val(), mod) == 1
@{keyword.complexity}
-
$O(1)$ (割り算以外) -
$O(\log \mathrm{mod})$ (割り算)
modint x.pow(ll n)
@{keyword.constraints}
$0 \le n$
@{keyword.complexity}
$O(\log n)$
modint x.inv()
@{keyword.constraints}
gcd(x.val(), mod) = 1
@{keyword.complexity}
$O(\log \mathrm{mod})$
modint modint::raw(int x)
x
に対してmodを取らずに、modint(x)
を返す。
定数倍高速化のための関数です。
上で述べたように
modint a;
int i;
a += i;
は、i
がmod以上でも動きます。勝手にi
に対してmodを取るためです。
ですが、たとえば以下のようなコードでは、i
がmodを超えないことを保証できます。
int main() {
modint::set_mod(1000000007);
modint a = 1;
for (int i = 1; i < 100000; i++) {
a += i;
}
}
このような時に、
int main() {
modint::set_mod(1000000007);
modint a = 1;
for (int i = 1; i < 100000; i++) {
a += modint::raw(i);
}
}
と書くと、modの回数を減らすことが出来ます。
当然ながらmodint::raw(x)
にmod以上の値を入れたときの挙動は未定義です。
@{keyword.constraints}
$0 \leq x \lt \mathrm{mod}$
問題文で他のmod (例: 1000000009
) が与えられる場合、以下のように書けます
using mint = static_modint<1000000009>;
modint998244353
, modint1000000007
は、static_modint<998244353>
, static_modint<1000000007>
のエイリアスになっています。
using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;
複数種類modを使用したい場合以下のようにできます
using mint0 = dynamic_modint<0>;
using mint1 = dynamic_modint<1>;
modint
は、dynamic_modint<-1>
のエイリアスになっています。
using modint = dynamic_modint<-1>;
@{example.modint_usage}