src/alfred/math/mod-int.hpp

• View this file on GitHub
• Last update: 2025-03-25 20:32:19+08:00
• Include: #include "src/alfred/math/mod-int.hpp"

Verified with

• verify/verify-yosupo-ds/yosupo-weighted-dsu.test.cpp

Code

#ifndef AFMT_MOD_INT
#define AFMT_MOD_INT

#include <iostream>

template <int mod>
inline int down(int x) { return x >= mod ? x - mod : x; }
template <int mod>
inline int up(int x) { return x < 0 ? x + mod : x; }
template <int mod>
struct ModInt {
    int x;
    ModInt(void) = default;
    ModInt(int x) : x(up<mod>(x)) {}
    ModInt(long long x) : x(x % mod) {}
    friend std::istream &operator>>(std::istream &in, ModInt &a) { return in >> a.x; }
    friend std::ostream &operator<<(std::ostream &out, ModInt a) { return out << a.x; }
    friend ModInt operator+(ModInt a, ModInt b) { return down<mod>(a.x + b.x); }
    friend ModInt operator-(ModInt a, ModInt b) { return down<mod>(a.x - b.x + mod); }
    friend ModInt operator*(ModInt a, ModInt b) { return (long long)a.x * b.x; }
    friend ModInt operator/(ModInt a, ModInt b) { return a * ~b; }
    friend ModInt operator^(ModInt a, long long b) {
        ModInt ans = 1;
        for (; b > 0; b >>= 1, a *= a)
            if (b & 1) ans *= a;
        return ans;
    }
    friend ModInt operator~(ModInt a) { return a ^ (mod - 2); }
    friend ModInt operator-(ModInt a) { return down<mod>(mod - a.x); }
    friend ModInt &operator+=(ModInt &a, ModInt b) { return a = a + b; }
    friend ModInt &operator-=(ModInt &a, ModInt b) { return a = a - b; }
    friend ModInt &operator*=(ModInt &a, ModInt b) { return a = a * b; }
    friend ModInt &operator/=(ModInt &a, ModInt b) { return a = a / b; }
    friend ModInt &operator^=(ModInt &a, long long b) { return a = a ^ b; }
    friend ModInt &operator++(ModInt &a) { return a += 1; }
    friend ModInt operator++(ModInt &a, int) {
        ModInt x = a;
        a += 1;
        return x;
    }
    friend ModInt &operator--(ModInt &a) { return a -= 1; }
    friend ModInt operator--(ModInt &a, int) {
        ModInt x = a;
        a -= 1;
        return x;
    }
    friend bool operator==(ModInt a, ModInt b) { return a.x == b.x; }
    friend bool operator!=(ModInt a, ModInt b) { return !(a == b); }
};
template <int mod>
inline void __print(ModInt<mod> x) {
    std::cerr << x;
}

using m998 = ModInt<998244353>;
using m107 = ModInt<1000000007>;

#endif // AFMT_MOD_INT

#line 1 "src/alfred/math/mod-int.hpp"


#ifndef AFMT_MOD_INT
#define AFMT_MOD_INT

#include <iostream>

template <int mod>
inline int down(int x) { return x >= mod ? x - mod : x; }
template <int mod>
inline int up(int x) { return x < 0 ? x + mod : x; }
template <int mod>
struct ModInt {
    int x;
    ModInt(void) = default;
    ModInt(int x) : x(up<mod>(x)) {}
    ModInt(long long x) : x(x % mod) {}
    friend std::istream &operator>>(std::istream &in, ModInt &a) { return in >> a.x; }
    friend std::ostream &operator<<(std::ostream &out, ModInt a) { return out << a.x; }
    friend ModInt operator+(ModInt a, ModInt b) { return down<mod>(a.x + b.x); }
    friend ModInt operator-(ModInt a, ModInt b) { return down<mod>(a.x - b.x + mod); }
    friend ModInt operator*(ModInt a, ModInt b) { return (long long)a.x * b.x; }
    friend ModInt operator/(ModInt a, ModInt b) { return a * ~b; }
    friend ModInt operator^(ModInt a, long long b) {
        ModInt ans = 1;
        for (; b > 0; b >>= 1, a *= a)
            if (b & 1) ans *= a;
        return ans;
    }
    friend ModInt operator~(ModInt a) { return a ^ (mod - 2); }
    friend ModInt operator-(ModInt a) { return down<mod>(mod - a.x); }
    friend ModInt &operator+=(ModInt &a, ModInt b) { return a = a + b; }
    friend ModInt &operator-=(ModInt &a, ModInt b) { return a = a - b; }
    friend ModInt &operator*=(ModInt &a, ModInt b) { return a = a * b; }
    friend ModInt &operator/=(ModInt &a, ModInt b) { return a = a / b; }
    friend ModInt &operator^=(ModInt &a, long long b) { return a = a ^ b; }
    friend ModInt &operator++(ModInt &a) { return a += 1; }
    friend ModInt operator++(ModInt &a, int) {
        ModInt x = a;
        a += 1;
        return x;
    }
    friend ModInt &operator--(ModInt &a) { return a -= 1; }
    friend ModInt operator--(ModInt &a, int) {
        ModInt x = a;
        a -= 1;
        return x;
    }
    friend bool operator==(ModInt a, ModInt b) { return a.x == b.x; }
    friend bool operator!=(ModInt a, ModInt b) { return !(a == b); }
};
template <int mod>
inline void __print(ModInt<mod> x) {
    std::cerr << x;
}

using m998 = ModInt<998244353>;
using m107 = ModInt<1000000007>;

#endif // AFMT_MOD_INT

Back to top page