7K12 blog

猫でも分かるアルゴリズム解説

NyaaLIB::NT_ModINT

MOD 型ライブラリ

#include <bits/stdc++.h>

namespace NyaaLIB
{
	/**
	* MOD 型ライブラリ
	**/

	template <long long mod> struct NT_ModINT
	{	// 非型テンプレートパラメータ
		using mint = NT_ModINT;
		using ll = long long;
		ll x;

		NT_ModINT() : x(0) {}
		NT_ModINT(ll init) : x(init% mod + mod) { if (x >= mod) x -= mod; }
		mint operator + () const { return x; }
		mint operator - () const { return (-x < 0) ? mod - x : -x; }
		mint& operator += (mint r) { if ((x += r.x) >= mod) x -= mod; return *this; }
		mint& operator -= (mint r) { if ((x -= r.x) < 0) x += mod; return *this; }
		mint& operator *= (mint r) {	x = (unsigned long long) x * r.x % mod; return *this; }
		mint& operator /= (mint r) { x = x * Inv(r.x, mod) % mod; return *this; }
		mint& operator += (ll r) { return *this += mint(r); }
		mint& operator -= (ll r) { return *this -= mint(r); }
		mint& operator *= (ll r) { return *this *= mint(r); }
		mint& operator /= (ll r) { return *this /= mint(r); }
		template <class T> mint operator + (T r) const { return mint(*this) += r; }
		template <class T> mint operator - (T r) const { return mint(*this) -= r; }
		template <class T> mint operator * (T r) const { return mint(*this) *= r; }
		template <class T> mint operator / (T r) const { return mint(*this) /= r; }
		friend ostream& operator << (ostream& s, mint a) { s << a.x, a.x %= mod; return s; }
		friend istream& operator >> (istream& s, mint& a) { s >> a.x, a.x %= mod; return s; }
		bool operator == (mint& r) const { return x == r.x; }
		bool operator != (mint& r) const { return x != r.x; }
		bool operator <  (mint& r) const { return x < r.x; }
		bool operator <= (mint& r) const { return x <= r.x; }
		bool operator >  (mint& r) const { return x > r.x; }
		bool operator >= (mint& r) const { return x >= r.x; }
		template <class T1, class T2> static mint Add(T1 l, T2 r) { return (mod == 0) ? 0 : mint(l) + mint(r); }
		template <class T1, class T2> static mint Sub(T1 l, T2 r) { return (mod == 0) ? 0 : mint(l) - mint(r); }
		template <class T1, class T2> static mint Mul(T1 l, T2 r) { return (mod == 0) ? 0 : mint(l) * mint(r); }
		template <class T1, class T2> static mint Div(T1 l, T2 r) { return (mod == 0) ? 0 : mint(l) / mint(r); }

		ll Inv(ll a, ll m)
		{	// 逆元 x^{-1} (主に除算演算子で使用)
			ll b = m, u = 1, v = 0;
			while (b)
			{
				ll t = a / b;
				a -= t * b; swap(a, b);
				u -= t * v; swap(u, v);
			}
			u %= m;
			return (u < 0) ? u + m : u;
		}

		template <class T1, class T2> static mint Pow(T1 x, T2 n)
		{	// 累乗(繰り返し二乗法) 計算量 O(log N)
			mint res = 1;
			if (0 < n)
			{
				res = Pow(x, n / 2);
				res = res * res;
				if (n % 2 != 0) res *= x;
			}
			return res;
		}
	};
}

実装例
https://atcoder.jp/contests/abc034/submissions/29800327