模板
int MOD;
// const int MOD = ;
struct ModInt {
int x;
ModInt(int x = 0) : x(x % MOD) {}
ModInt(long long x) : x (x % MOD) {}
int val() { return x; }
ModInt operator + (const ModInt &a) const { int x0 = x + a.x; return ModInt(x0 < MOD ? x0 : x0 - MOD); }
ModInt operator - (const ModInt &a) const { int x0 = x - a.x; return ModInt(x0 < MOD ? x0 + MOD : x0); }
ModInt operator * (const ModInt &a) const { return ModInt(1LL * x * a.x % MOD); }
ModInt operator / (const ModInt &a) const { return *this * a.inv(); }
void operator += (const ModInt &a) { x += a.x; if (x >= MOD) x -= MOD; }
void operator -= (const ModInt &a) { x -= a.x; if (x < 0) x += MOD; }
void operator *= (const ModInt &a) { x = 1LL * x * a.x % MOD; }
void operator /= (const ModInt &a) { *this = *this / a; }
ModInt qpow(long long n) const { ModInt res(1), mul(x);for (; n; n>>=1, mul *= mul)if (n & 1) res *= mul;return res; }
ModInt inv() const { return qpow(MOD-2); }
friend std::ostream &operator<<(std::ostream &os, const ModInt &a) { return os << a.x;}
};
使用
变量做模数时,使用 int MOD
,常数做模数时,使用 const int MOD
。
可以像 int
一样使用。
支持的运算 :
+
-
*
/
+=
-=
*=
/=
qpow(n)
快速幂inv()
逆元
可以使用 std::cout
直接输出