ホーム > libalgo

MOD 取り構造体

概要

mod M での四則演算を行う構造体.

注意

  • $0^0$, $a/0$ は何が起こるかわからない
  • mint * int はコンパイルが通るが int * mint はエラーになる
  • ほとんど $O(1)$ で /, inv, pow は log 時間
  • 定数倍はかなり重い

実装

template <int M>
struct mod_int {
    int x;
    mod_int() : x(0) {}
    mod_int(int y) : x(y >= 0 ? y % M : M - (-y) % M) {}
    mod_int &operator+=(const mod_int &rhs) {
        if ((x += rhs.x) >= M) x -= M;
        return *this;
    }
    mod_int &operator-=(const mod_int &rhs) {
        if ((x += M - rhs.x) >= M) x -= M;
        return *this;
    }
    mod_int &operator*=(const mod_int &rhs) {
        x = 1LL * x * rhs.x % M;
        return *this;
    }
    mod_int &operator/=(const mod_int &rhs) {
        x = (1LL * x * rhs.inv().x) % M;
        return *this;
    }
    mod_int operator-() const { return mod_int(-x); }
    mod_int operator+(const mod_int &rhs) const { return mod_int(*this) += rhs; }
    mod_int operator-(const mod_int &rhs) const { return mod_int(*this) -= rhs; }
    mod_int operator*(const mod_int &rhs) const { return mod_int(*this) *= rhs; }
    mod_int operator/(const mod_int &rhs) const { return mod_int(*this) /= rhs; }
    bool operator<(const mod_int &rhs) const { return x < rhs.x; }
    mod_int inv() const {
        signed a = x, b = M, u = 1, v = 0, t;
        while (b) {
            t = a / b;
            a -= t * b;
            std::swap(a, b);
            u -= t * v;
            std::swap(u, v);
        }
        return mod_int(u);
    }
    mod_int pow(long long t) const {
        mod_int e = *this, res = 1;
        for (; t; e *= e, t >>= 1)
            if (t & 1) res *= e;
        return res;
    }
};
template <int M>
std::ostream &operator<<(std::ostream &os, const mod_int<M> &rhs) {
    return os << rhs.x;
}
template <int M>
std::istream &operator>>(std::istream &is, mod_int<M> &rhs) {
    long long s;
    is >> s;
    rhs = mod_int<M>(s);
    return is;
};

using mint = mod_int<MOD>;