Modint

It is the struct that treats the modular arithmetic. All the remaining parts of AC Library works without modint, so you don't necessarily read this to use the remaining parts.

For most of the problems, it is sufficient to use modint998244353, modint1000000007, or modint, which can be used as follows.

#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;
}

If the mod is not fixed, you can use modint as follows.

#include <atcoder/modint>
#include <iostream>

using namespace std;

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;
}

All the functions except set_mod work for all three of them.

Constructor

(1) modint x()
(2) modint x<T>(T y)

set_mod

void modint::set_mod(int m)

It sets the mod. It must be called first.

Constraints

Complexity

mod

int modint::mod()

It returns the mod.

val

int x.val();

It returns the value that is stored in x.

Operations

The following operations work.

-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;

The following also works, because it is interpreted as modint(1) + x.

modint x = 10;
1 + x;

The following also works, because it is interpreted as y * modint(z).

modint::set_mod(11);
modint y = 10;
int z = 1234;
y * z;

Constraints

Complexity

pow

modint x.pow(ll n)

It returns $x^n$.

Constraints

Complexity

inv

modint x.inv()

It returns $y$ with $xy \equiv 1$.

Constraints

Complexity

raw

modint modint::raw(int x)

It returns modint(x) without taking mod. It is the function for constant-factor speedup.

For example, the following code works even if i is greater than or equal to mod, because mod is automatically taken.

modint a;
int i;
a += i;

However, in the following code, it is ensured that i is less than mod.

int main() {
    modint::set_mod(1000000007);
    modint a = 1;
    for (int i = 1; i < 100000; i++) {
        a += i;
    }
}

In such a situation, we can decrease the number of mod operations as follows.

int main() {
    modint::set_mod(1000000007);
    modint a = 1;
    for (int i = 1; i < 100000; i++) {
        a += modint::raw(i);
    }
}

When the value more than or equal to mod is assigned to modint::raw(x), the behavior is undefined.

Constraints

Tips (other mod)

You can use the other fixed mod like 1000000009 as follows.

using mint = static_modint<1000000009>;

modint998244353 (resp. modint1000000007) is the alias of static_modint<998244353> (resp. static_modint<1000000007>).

using modint998244353 = static_modint<998244353>;
using modint1000000007 = static_modint<1000000007>;

Tips (multiple mods)

You can use multiple mods as follows.

using mint0 = dynamic_modint<0>;
using mint1 = dynamic_modint<1>;

modint is the alias of dynamic_modint<-1>.

using modint = dynamic_modint<-1>;

Examples

How to Use

#include <atcoder/modint> #include <cstdio> using namespace std; using namespace atcoder; using mint = static_modint<11>; int main() { mint a = 10; mint b(3); // equal assert(a == 21); assert(a == -1); assert(-1 == a); // negative assert(-b == 8); // plus assert(a + b == 2); // (10 + 3) mod 11 assert(1 + a == 0); // minus assert(a - b == 7); // (10 - 3) mod 11 assert(b - a == 4); // mul assert(a * b == 8); // (10 * 3) mod 11 // inv assert(b.inv() == 4); // (3 * 4) mod 11 == 1 // div assert(a / b == 7); // (10 * 4) mod 11 // +=, -=, *=, /= a += b; assert(a == 2 && b == 3); a -= b; assert(a == 10 && b == 3); a *= b; assert(a == 8 && b == 3); a /= b; assert(a == 10 && b == 3); // pow assert(mint(2).pow(4) == 5); // 16 mod 11 // print value printf("%d\n", a.val()); // 10 // get mod assert(mint::mod() == 11 && a.mod() == 11); // mint(x) と書くとmodを取る操作が発生します((x % mod + mod) % modをmodintに代入します) // mint::raw(x) はxをmodを取らずに代入するので高速です(もちろんxが[0, mod)であることを利用者が保証しないといけません) assert(mint::raw(3) == 3); }