ModInt (mod/modint.cpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2023-08-27 23:50:55+09:00

なにこれ

演算時に $\bmod$ を自動でとってくれる． 基本的に Integer と同様に扱えるはず． ModInt と Integer の演算もできる（下記参照）．

コンストラクタ

• modint<mod>(x)：mod を法としたときの x．除算を使う場合，mod は素数である必要がある．

補足

以下の演算子に対応している．

• 算術演算
  • 四則演算 +, -, *, /
  • インクリメント・デクリメント（前置・後置）
  • 複合代入 +=, -=, *=, /=
  • 単項マイナス　-a みたいなやつ
• 比較演算 ==, !=, <, >, <=, >=
• 単純代入 =
• 入出力 >>, <<

除算 /, /= は計算量 $O(\log x)$ かかることに注意．

Verified with

• test/aoj_0341.cpp
• test/yuki_0599.cpp
• test/yuki_1035.cpp

Code

#pragma once

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

template<int mod> struct modint {
private:
	long long val;

public:
	modint(long long x = 0) : val((mod + x % mod) % mod) {}

private:
	modint inv() const {
		long long x_ = val, xd = 1, xdd = 0, y_ = mod, yd = 0, ydd = 1, div;

		while(true) {
			if(!y_) return modint(xd);
			div = x_ / y_;
			x_ -= div * y_;
			xd -= div * yd;
			xdd -= div * ydd;

			if(!x_) return modint(yd);
			div = y_ / x_;
			y_ -= div * x_;
			yd -= div * xd;
			ydd -= div * xdd;
		}
	}

public:
	modint operator-() const {
		return modint(-val);
	}

	modint &operator+=(const modint &a) {
		val += a.val;
		if(val >= mod) val -= mod;
		return *this;
	}
	modint &operator-=(const modint &a) {
		val -= a.val;
		if(val < 0) val += mod;
		return *this;
	}
	modint &operator*=(const modint &a) {
		(val *= a.val) %= mod;
		return *this;
	}
	modint &operator/=(const modint &a) {
		return (*this) *= a.inv();
	}
	modint &operator+=(const long long &a) {
		(val += mod + a % mod) %= mod;
		return *this;
	}
	modint &operator-=(const long long &a) {
		(val += mod - a % mod) %= mod;
		return *this;
	}
	modint &operator*=(const long long &a) {
		(val *= mod + a % mod) %= mod;
		return *this;
	}
	modint &operator/=(const long long &a) {
		return (*this) /= modint(a);
	}

	modint operator+(const modint &a) const {
		return modint(*this) += a;
	}
	modint operator-(const modint &a) const {
		return modint(*this) -= a;
	}
	modint operator*(const modint &a) const {
		return modint(*this) *= a;
	}
	modint operator/(const modint &a) const {
		return modint(*this) /= a;
	}
	modint operator+(const long long &a) const {
		return modint(*this) += a;
	}
	modint operator-(const long long &a) const {
		return modint(*this) -= a;
	}
	modint operator*(const long long &a) const {
		return modint(*this) *= a;
	}
	modint operator/(const long long &a) const {
		return modint(*this) /= modint(a);
	}

	modint &operator++() {
		(++val) %= mod;
		return *this;
	}
	modint operator++(int) {
		modint res(*this);
		(++val) %= mod;
		return res;
	}
	modint &operator--() {
		(val += mod - 1) %= mod;
		return *this;
	}
	modint operator--(int) {
		modint res(*this);
		(val += mod - 1) %= mod;
		return res;
	}

	bool operator==(const modint &a) const {
		return val == a.val;
	}
	bool operator!=(const modint &a) const {
		return val != a.val;
	}
	bool operator<(const modint &a) const {
		return val < a.val;
	}
	bool operator>(const modint &a) const {
		return val > a.val;
	}
	bool operator<=(const modint &a) const {
		return val <= a.val;
	}
	bool operator>=(const modint &a) const {
		return val >= a.val;
	}
	bool operator==(const long long &a) const {
		return val == a;
	}
	bool operator!=(const long long &a) const {
		return val != a;
	}
	bool operator<(const long long &a) const {
		return val < a;
	}
	bool operator>(const long long &a) const {
		return val > a;
	}
	bool operator<=(const long long &a) const {
		return val <= a;
	}
	bool operator>=(const long long &a) const {
		return val >= a;
	}

	modint &operator=(const modint &a) {
		val = a.val;
		return *this;
	}
	modint &operator=(const long long &a) {
		val = (mod + a % mod) % mod;
		return *this;
	}

	friend ostream &operator<<(ostream &os, const modint &a) {
		return os << a.val;
	}
	friend istream &operator>>(istream &is, modint &a) {
		long long n;
		is >> n;
		a = modint(n);
		return is;
	}
};
using mint = modint<998244353>;

#line 2 "mod/modint.cpp"

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

template<int mod> struct modint {
private:
	long long val;

public:
	modint(long long x = 0) : val((mod + x % mod) % mod) {}

private:
	modint inv() const {
		long long x_ = val, xd = 1, xdd = 0, y_ = mod, yd = 0, ydd = 1, div;

		while(true) {
			if(!y_) return modint(xd);
			div = x_ / y_;
			x_ -= div * y_;
			xd -= div * yd;
			xdd -= div * ydd;

			if(!x_) return modint(yd);
			div = y_ / x_;
			y_ -= div * x_;
			yd -= div * xd;
			ydd -= div * xdd;
		}
	}

public:
	modint operator-() const {
		return modint(-val);
	}

	modint &operator+=(const modint &a) {
		val += a.val;
		if(val >= mod) val -= mod;
		return *this;
	}
	modint &operator-=(const modint &a) {
		val -= a.val;
		if(val < 0) val += mod;
		return *this;
	}
	modint &operator*=(const modint &a) {
		(val *= a.val) %= mod;
		return *this;
	}
	modint &operator/=(const modint &a) {
		return (*this) *= a.inv();
	}
	modint &operator+=(const long long &a) {
		(val += mod + a % mod) %= mod;
		return *this;
	}
	modint &operator-=(const long long &a) {
		(val += mod - a % mod) %= mod;
		return *this;
	}
	modint &operator*=(const long long &a) {
		(val *= mod + a % mod) %= mod;
		return *this;
	}
	modint &operator/=(const long long &a) {
		return (*this) /= modint(a);
	}

	modint operator+(const modint &a) const {
		return modint(*this) += a;
	}
	modint operator-(const modint &a) const {
		return modint(*this) -= a;
	}
	modint operator*(const modint &a) const {
		return modint(*this) *= a;
	}
	modint operator/(const modint &a) const {
		return modint(*this) /= a;
	}
	modint operator+(const long long &a) const {
		return modint(*this) += a;
	}
	modint operator-(const long long &a) const {
		return modint(*this) -= a;
	}
	modint operator*(const long long &a) const {
		return modint(*this) *= a;
	}
	modint operator/(const long long &a) const {
		return modint(*this) /= modint(a);
	}

	modint &operator++() {
		(++val) %= mod;
		return *this;
	}
	modint operator++(int) {
		modint res(*this);
		(++val) %= mod;
		return res;
	}
	modint &operator--() {
		(val += mod - 1) %= mod;
		return *this;
	}
	modint operator--(int) {
		modint res(*this);
		(val += mod - 1) %= mod;
		return res;
	}

	bool operator==(const modint &a) const {
		return val == a.val;
	}
	bool operator!=(const modint &a) const {
		return val != a.val;
	}
	bool operator<(const modint &a) const {
		return val < a.val;
	}
	bool operator>(const modint &a) const {
		return val > a.val;
	}
	bool operator<=(const modint &a) const {
		return val <= a.val;
	}
	bool operator>=(const modint &a) const {
		return val >= a.val;
	}
	bool operator==(const long long &a) const {
		return val == a;
	}
	bool operator!=(const long long &a) const {
		return val != a;
	}
	bool operator<(const long long &a) const {
		return val < a;
	}
	bool operator>(const long long &a) const {
		return val > a;
	}
	bool operator<=(const long long &a) const {
		return val <= a;
	}
	bool operator>=(const long long &a) const {
		return val >= a;
	}

	modint &operator=(const modint &a) {
		val = a.val;
		return *this;
	}
	modint &operator=(const long long &a) {
		val = (mod + a % mod) % mod;
		return *this;
	}

	friend ostream &operator<<(ostream &os, const modint &a) {
		return os << a.val;
	}
	friend istream &operator>>(istream &is, modint &a) {
		long long n;
		is >> n;
		a = modint(n);
		return is;
	}
};
using mint = modint<998244353>;

Back to top page