src/modint.hpp

• View this file on GitHub
• Last update: 2025-10-08 00:44:44+09:00
• Include: #include "src/modint.hpp"

Depends on

• src/template.hpp

Required by

• src/binomial.hpp
• src/test/atc_abc357_f.cpp

Code

#pragma once
#include "template.hpp"

template<int mod = 998244353> struct modint {
    int x;
    constexpr modint(long x_ = 0): x(x_ % mod) {
        if(x < 0) x += mod;
    }
    constexpr modint operator-() {
        auto res = *this;
        res.x = (x ? mod - x : 0);
        return res;
    }
    constexpr modint& operator+=(modint r) {
        if((x += r.x) >= mod) x -= mod;
        return *this;
    }
    constexpr modint& operator-=(modint r) {
        if((x -= r.x) < 0) x += mod;
        return *this;
    }
    constexpr modint& operator*=(modint r) {
        x = 1LL * x * r.x % mod;
        return *this;
    }
    constexpr modint& operator/=(modint r) { return *this *= r.inv(); }
    constexpr friend modint operator+(modint a, modint b) { return a += b; }
    constexpr friend modint operator-(modint a, modint b) { return a -= b; }
    constexpr friend modint operator*(modint a, modint b) { return a *= b; }
    constexpr friend modint operator/(modint a, modint b) { return a /= b; }
    constexpr modint inv() const { return pow(mod - 2); }
    constexpr modint pow(long b) const {
        assert(0 <= b);
        modint a = *this, c = 1;
        while(b) {
            if(b & 1) c *= a;
            a *= a;
            b >>= 1;
        }
        return c;
    }
    constexpr int val() const { return x; }
    constexpr friend ostream& operator<<(ostream& os, const modint& m) { return os << m.val(); }

    constexpr friend istream& operator>>(istream& is, modint& m) {
        long v;
        is >> v;
        m = modint(v);
        return is;
    }
};
using mint = modint<>;

#line 2 "src/template.hpp"
#include <bits/stdc++.h>
using namespace std;
#define si(a) (long)a.size()
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define rep(i, n) for(long i = 0; i < (long)(n); ++i)
template<typename T> bool chmin(T& a, T b) { return b < a ? (a = b, 1) : 0; }
template<typename T> bool chmax(T& a, T b) { return b > a ? (a = b, 1) : 0; }
struct _ {
    _() { cin.tie(0)->sync_with_stdio(0), cout.tie(0), cout << fixed << setprecision(16); }
} __;
#line 3 "src/modint.hpp"

template<int mod = 998244353> struct modint {
    int x;
    constexpr modint(long x_ = 0): x(x_ % mod) {
        if(x < 0) x += mod;
    }
    constexpr modint operator-() {
        auto res = *this;
        res.x = (x ? mod - x : 0);
        return res;
    }
    constexpr modint& operator+=(modint r) {
        if((x += r.x) >= mod) x -= mod;
        return *this;
    }
    constexpr modint& operator-=(modint r) {
        if((x -= r.x) < 0) x += mod;
        return *this;
    }
    constexpr modint& operator*=(modint r) {
        x = 1LL * x * r.x % mod;
        return *this;
    }
    constexpr modint& operator/=(modint r) { return *this *= r.inv(); }
    constexpr friend modint operator+(modint a, modint b) { return a += b; }
    constexpr friend modint operator-(modint a, modint b) { return a -= b; }
    constexpr friend modint operator*(modint a, modint b) { return a *= b; }
    constexpr friend modint operator/(modint a, modint b) { return a /= b; }
    constexpr modint inv() const { return pow(mod - 2); }
    constexpr modint pow(long b) const {
        assert(0 <= b);
        modint a = *this, c = 1;
        while(b) {
            if(b & 1) c *= a;
            a *= a;
            b >>= 1;
        }
        return c;
    }
    constexpr int val() const { return x; }
    constexpr friend ostream& operator<<(ostream& os, const modint& m) { return os << m.val(); }

    constexpr friend istream& operator>>(istream& is, modint& m) {
        long v;
        is >> v;
        m = modint(v);
        return is;
    }
};
using mint = modint<>;

Back to top page