library/math/modint.hpp

• View this file on GitHub
• Last update: 2025-10-31 18:20:20+09:00
• Include: #include "library/math/modint.hpp"

Depends on

• library/template/template.hpp

Code

#pragma once

#include "../template/template.hpp"
const ll mod = mod2;
struct mint {
	ll x;
	mint(ll y = 0) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
	mint &operator+=(const mint &p) {
		if ((x += p.x) >= mod) x -= mod;
		return *this;
	}
	mint &operator-=(const mint &p) {
		if ((x += mod - p.x) >= mod) x -= mod;
		return *this;
	}
	mint &operator*=(const mint &p) {
		x = (ll)(1ll * x * p.x % mod);
		return *this;
	}
	mint &operator/=(const mint &p) {
		*this *= p.inv();
		return *this;
	}
	mint operator-() const { return mint(-x); }
	mint operator+(const mint &p) const { return mint(*this) += p; }
	mint operator-(const mint &p) const { return mint(*this) -= p; }
	mint operator*(const mint &p) const { return mint(*this) *= p; }
	mint operator/(const mint &p) const { return mint(*this) /= p; }
	bool operator==(const mint &p) const { return x == p.x; }
	bool operator!=(const mint &p) const { return x != p.x; }
	friend ostream &operator<<(ostream &os, const mint &p) { return os << p.x; }
	friend istream &operator>>(istream &is, mint &a) {
		ll t; is >> t; a = mint(t); return (is);
	}
	mint inv() const { return pow(mod - 2); }
	mint pow(ll n) const {
		mint ret(1), mul(x);
		while (n > 0) {
			if (n & 1) ret *= mul;
			mul *= mul;
			n >>= 1;
		}
		return ret;
	}
};

#line 2 "library/math/modint.hpp"

#line 2 "library/template/template.hpp"

#include <bits/stdc++.h>
using namespace std;
#define MM << ' ' <<
using ll = long long;
using ld = long double;
using pll = pair<ll, ll>;
using vl = vector<ll>;
template <class T> using vec = vector<T>;
template <class T> using vv = vec<vec<T>>;
template <class T> using vvv = vv<vec<T>>;
template <class T> using minpq = priority_queue<T, vector<T>, greater<T>>;
#define rep(i, r) for(ll i = 0; i < (r); i++)
#define reps(i, l, r) for(ll i = (l); i < (r); i++)
#define rrep(i, l, r) for(ll i = (r) - 1; i >= l; i--)
template <class T> void uniq(T &a) { sort(all(a)); erase(unique(all(a)), a.end()); }
#define all(a) (a).begin(), (a).end()
#define sz(a) (ll)(a).size()
const ll INF = numeric_limits<ll>::max() / 4;
const ld inf = numeric_limits<ld>::max() / 2;
const ll mod1 = 1000000007;
const ll mod2 = 998244353;
const ld pi = 3.141592653589793238;
template <class T> void rev(T &a) { reverse(all(a)); }
ll popcnt(ll a) { return __builtin_popcountll(a); }
template<typename T>
bool chmax(T &a, const T& b) { return a < b ? a = b, true : false; }
template<typename T>
bool chmin(T &a, const T& b) { return a > b ? a = b, true : false; }
template <typename T1, typename T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
	os << p.first << " " << p.second;
	return os;
}
template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& p) {
	is >> p.first >> p.second;
	return is;
}
template <typename T>
ostream& operator<<(ostream& os, const vec<T>& v) {
	rep(i, sz(v)) {
		os << v[i] << " \n"[i + 1 == sz(v)];
	}
	return os;
}
template <typename T>
istream& operator>>(istream& is, vec<T>& v) {
	for (T& in : v) is >> in;
	return is;
}
void yesno(bool t) {
	cout << (t ? "Yes" : "No") << endl;
}
#line 4 "library/math/modint.hpp"
const ll mod = mod2;
struct mint {
	ll x;
	mint(ll y = 0) : x(y >= 0 ? y % mod : (mod - (-y) % mod) % mod) {}
	mint &operator+=(const mint &p) {
		if ((x += p.x) >= mod) x -= mod;
		return *this;
	}
	mint &operator-=(const mint &p) {
		if ((x += mod - p.x) >= mod) x -= mod;
		return *this;
	}
	mint &operator*=(const mint &p) {
		x = (ll)(1ll * x * p.x % mod);
		return *this;
	}
	mint &operator/=(const mint &p) {
		*this *= p.inv();
		return *this;
	}
	mint operator-() const { return mint(-x); }
	mint operator+(const mint &p) const { return mint(*this) += p; }
	mint operator-(const mint &p) const { return mint(*this) -= p; }
	mint operator*(const mint &p) const { return mint(*this) *= p; }
	mint operator/(const mint &p) const { return mint(*this) /= p; }
	bool operator==(const mint &p) const { return x == p.x; }
	bool operator!=(const mint &p) const { return x != p.x; }
	friend ostream &operator<<(ostream &os, const mint &p) { return os << p.x; }
	friend istream &operator>>(istream &is, mint &a) {
		ll t; is >> t; a = mint(t); return (is);
	}
	mint inv() const { return pow(mod - 2); }
	mint pow(ll n) const {
		mint ret(1), mul(x);
		while (n > 0) {
			if (n & 1) ret *= mul;
			mul *= mul;
			n >>= 1;
		}
		return ret;
	}
};

Back to top page