7K12B blog

猫でも分かる何か

mod型ライブラリ LIB::NT_ModINT

template<class T1, class T2>static mint Pow(T1 x, T2 n)

繰り返し二乗法で  x^n を計算する 計算量  O(\log n)

namespace LIB {
	template<long long mod>class ModINT {
		using mint=ModINT;
		using ll=long long;
		ll inv(ll a, ll m) {
			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;
		}
	public:
		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); }

		template<class T1, class T2>static mint Pow(T1 x, T2 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/45429293