icpc/modint.hpp

• View this file on GitHub
• Last update: 2023-05-31 02:53:46+09:00
• Include: #include "icpc/modint.hpp"
• Link: https://onlinejudge.u-aizu.ac.jp/problems/2751
• Link: https://onlinejudge.u-aizu.ac.jp/problems/3331

Depends on

• icpc/template.hpp

Verified with

• verify/aoj_other/aoj_2751.test.cpp

Code

#pragma once

#include "icpc/template.hpp"

// https://onlinejudge.u-aizu.ac.jp/problems/3331
// https://onlinejudge.u-aizu.ac.jp/problems/2751

template <uint MD> struct Modint {
    using M = Modint;
    const static M G;
    uint v;
    Modint(ll val = 0) { set_v(val % MD + MD); }
    M& set_v(uint val) {
        v = (val < MD) ? val : val - MD;
        return *this;
    }
    explicit operator bool() const { return v != 0; }
    M operator-() const { return M() - *this; }
    M operator+(const M& r) const { return M().set_v(v + r.v); }
    M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
    M operator*(const M& r) const { return M().set_v(ull(v) * r.v % MD); }
    M operator/(const M& r) const { return *this * r.inv(); }
    M& operator+=(const M& r) { return *this = *this + r; }
    M& operator-=(const M& r) { return *this = *this - r; }
    M& operator*=(const M& r) { return *this = *this * r; }
    M& operator/=(const M& r) { return *this = *this / r; }
    bool operator==(const M& r) const { return v == r.v; }
    M pow(ll n) const {
        M x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    M inv() const { return pow(MD - 2); }
    friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};
// using mint = Modint<998244353>;
// template<> const mint mint::G = mint(3);

#line 2 "icpc/modint.hpp"

#line 2 "icpc/template.hpp"

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
#define REP(i, n) for (int i = 0; i < (n); i++)
template <class T> using V = vector<T>;
template <class T> ostream& operator<<(ostream& os, const V<T>& v) {
    os << "[ ";
    for (auto& vi : v) os << vi << ", ";
    return os << "]";
}

#ifdef LOCAL
#define show(x) cerr << __LINE__ << " : " << #x << " = " << x << endl;
#else
#define show(x) true
#endif

using uint = unsigned int;
using ull = unsigned long long;

// g++ -g -fsanitize=undefined,address -DLOCAL -std=gnu++17
#line 4 "icpc/modint.hpp"

// https://onlinejudge.u-aizu.ac.jp/problems/3331
// https://onlinejudge.u-aizu.ac.jp/problems/2751

template <uint MD> struct Modint {
    using M = Modint;
    const static M G;
    uint v;
    Modint(ll val = 0) { set_v(val % MD + MD); }
    M& set_v(uint val) {
        v = (val < MD) ? val : val - MD;
        return *this;
    }
    explicit operator bool() const { return v != 0; }
    M operator-() const { return M() - *this; }
    M operator+(const M& r) const { return M().set_v(v + r.v); }
    M operator-(const M& r) const { return M().set_v(v + MD - r.v); }
    M operator*(const M& r) const { return M().set_v(ull(v) * r.v % MD); }
    M operator/(const M& r) const { return *this * r.inv(); }
    M& operator+=(const M& r) { return *this = *this + r; }
    M& operator-=(const M& r) { return *this = *this - r; }
    M& operator*=(const M& r) { return *this = *this * r; }
    M& operator/=(const M& r) { return *this = *this / r; }
    bool operator==(const M& r) const { return v == r.v; }
    M pow(ll n) const {
        M x = *this, r = 1;
        while (n) {
            if (n & 1) r *= x;
            x *= x;
            n >>= 1;
        }
        return r;
    }
    M inv() const { return pow(MD - 2); }
    friend ostream& operator<<(ostream& os, const M& r) { return os << r.v; }
};
// using mint = Modint<998244353>;
// template<> const mint mint::G = mint(3);

Back to top page