数据类型

大数类

struct Bigint 
{
	int sign; string digits;
	/*====================*/
	Bigint(void) {}
	Bigint(string b) { (*this) = b; }
	Bigint(int b) { (*this) = to_string(b); }
	/*====================*/
	int size(void) 
	{
		return digits.size();
	}
	Bigint inverseSign(void) 
	{ 
		sign *= -1; return (*this);
	}
	Bigint normalize(int newSign) 
	{ 
		for (int i = digits.size() - 1; i > 0 && digits[i] == '0'; i--)
		{
			digits.erase(digits.begin() + i);
		}
		sign = (digits.size() == 1 && digits[0] == '0') ? 1 : newSign; return (*this);
	}
	/*====================*/
	void operator = (string b) 
	{ 
		digits = b[0] == '-' ? b.substr(1) : b;
		reverse(digits.begin(), digits.end());
		this->normalize(b[0] == '-' ? -1 : 1);
	}
	/*====================*/
	bool operator < (const Bigint& b) const 
	{ 
		if (sign != b.sign) return sign < b.sign;
		if (digits.size() != b.digits.size())
			return sign == 1 ? digits.size() < b.digits.size() : digits.size() > b.digits.size();
		for (int i = digits.size() - 1; i >= 0; i--) if (digits[i] != b.digits[i])
			return sign == 1 ? digits[i] < b.digits[i] : digits[i] > b.digits[i];
		return false;
	}
	bool operator == (const Bigint& b) const 
	{
		return digits == b.digits && sign == b.sign;
	}
	/*====================*/
	Bigint operator + (Bigint b) 
	{ 
		if (sign != b.sign) return (*this) - b.inverseSign();
		Bigint c;
		for (int i = 0, carry = 0; i < digits.size() || i < b.size() || carry; i++) {
			carry += (i < digits.size() ? digits[i] - 48 : 0) + (i < b.digits.size() ? b.digits[i] - 48 : 0);
			c.digits += (carry % 10 + 48);
			carry /= 10;
		}
		return c.normalize(sign);
	}
	Bigint operator - (Bigint b) 
	{ 
		if (sign != b.sign) return (*this) + b.inverseSign();
		int s = sign; sign = b.sign = 1;
		if ((*this) < b) return ((b - (*this)).inverseSign()).normalize(-s);
		Bigint c;
		for (int i = 0, borrow = 0; i < digits.size(); i++) {
			borrow = digits[i] - borrow - (i < b.size() ? b.digits[i] : 48);
			c.digits += borrow >= 0 ? borrow + 48 : borrow + 58;
			borrow = borrow >= 0 ? 0 : 1;
		}
		return c.normalize(s);
	}
	Bigint operator * (Bigint b) 
	{ 
		Bigint c("0");
		for (int i = 0, k = digits[i] - 48; i < digits.size(); i++, k = digits[i] - 48) {
			while (k--) c = c + b;
			b.digits.insert(b.digits.begin(), '0');
		}
		return c.normalize(sign * b.sign);
	}
	Bigint operator / (Bigint b) 
	{
		if (b.size() == 1 && b.digits[0] == '0') b.digits[0] /= (b.digits[0] - 48);
		Bigint c("0"), d;
		for (int j = 0; j < digits.size(); j++) d.digits += "0";
		int dSign = sign * b.sign; b.sign = 1;
		for (int i = digits.size() - 1; i >= 0; i--) {
			c.digits.insert(c.digits.begin(), '0');
			c = c + digits.substr(i, 1);
			while (!(c < b)) c = c - b, d.digits[i]++;
		}
		return d.normalize(dSign);
	}
	Bigint operator % (Bigint b) 
	{
		if (b.size() == 1 && b.digits[0] == '0') b.digits[0] /= (b.digits[0] - 48);
		Bigint c("0");
		b.sign = 1;
		for (int i = digits.size() - 1; i >= 0; i--) {
			c.digits.insert(c.digits.begin(), '0');
			c = c + digits.substr(i, 1);
			while (!(c < b)) c = c - b;
		}
		return c.normalize(sign);
	}
	/*====================*/
	friend ostream& operator<<(ostream& output, Bigint integer)
	{
		if (integer.sign == -1) output << "-";
		for (int i = integer.digits.size() - 1; i >= 0; i--)
		{
			output << integer.digits[i];
		}
		return output;
	}
	friend istream& operator>>(istream& input, Bigint& integer)
	{
		string str; input >> str; integer = str; return input;
	}
};

分数类

class Fraction
{
public:
	int up, dw;
private:
	int GCD(int a, int b)
	{
		return b == 0 ? a : GCD(b, a % b);
	}
	void Simplest(void)
	{
		int divisor = GCD(up, dw);
		if (divisor != 0)
		{
			up /= divisor, dw /= divisor;
			if (dw < 0)dw *= -1, up *= -1;
		}
	}
public:
	Fraction(const Fraction& temp)
	{
		up = temp.up, dw = temp.dw;
	}
	Fraction(int _up = 0, int _dw = 1)
	{
		up = _up, dw = _dw; Simplest();
	}
	/*====================*/
	double Val(void)
	{
		return double(up) / double(dw);
	}
	/*====================*/
	void operator+=(const Fraction& x)
	{
		up = up * x.dw + x.up * dw; dw = dw * x.dw; Simplest();
	}
	void operator-=(const Fraction& x)
	{
		up = up * x.dw - x.up * dw; dw = dw * x.dw; Simplest();
	}
	void operator*=(const Fraction& x)
	{
		up = up * x.up; dw = dw * x.dw; Simplest();
	}
	void operator/=(const Fraction& x)
	{
		up = up * x.dw; dw = dw * x.up; Simplest();
	}
	/*====================*/
	friend Fraction operator+(const Fraction& a, const Fraction& b)
	{
		return Fraction(a.up * b.dw + b.up * a.dw, a.dw * b.dw);
	}
	friend Fraction operator-(const Fraction& a, const Fraction& b)
	{
		return Fraction(a.up * b.dw - b.up * a.dw, a.dw * b.dw);
	}
	friend Fraction operator*(const Fraction& a, const Fraction& b)
	{
		return Fraction(a.up * b.up, a.dw * b.dw);
	}
	friend Fraction operator/(const Fraction& a, const Fraction& b)
	{
		return Fraction(a.up * b.dw, a.dw * b.up);
	}
	/*====================*/
	friend bool operator<(const Fraction& a, const Fraction& b)
	{
		return (a.up * b.dw) < (b.up * a.dw);
	}
	friend bool operator>(const Fraction& a, const Fraction& b)
	{
		return (a.up * b.dw) > (b.up * a.dw);
	}
	friend bool operator==(const Fraction& a, const Fraction& b)
	{
		return (a.up == b.up) && (a.dw == b.dw);
	}
	friend bool operator!=(const Fraction& a, const Fraction& b)
	{
		return !(a == b);
	}
	friend bool operator<=(const Fraction& a, const Fraction& b)
	{
		return !(a > b);
	}
	friend bool operator>=(const Fraction& a, const Fraction& b)
	{
		return !(a < b);
	}
};

模数类

template<int MOD = 998244353>
class Modulo
{
private:
	static int Pow(int a, int b)
	{
		int res = 1;
		while (b)
		{
			if (b & 1)
			{
				res = (1ll * res * a) % MOD;
			}
			b >>= 1, a = (1ll * a * a) % MOD;
		}
		return res;
	}
	static int Inv(int x)
	{
		return Pow(x, MOD - 2);
	}
public:
	int num;
	/*====================*/
	Modulo(int temp = 0)
	{
		num = temp % MOD;
	}
	Modulo(const Modulo& temp)
	{
		num = temp.num;
	}
	/*====================*/
	friend Modulo operator+(const Modulo& a, const Modulo& b)
	{
		return Modulo((a.num + b.num) >= MOD ? a.num + b.num - MOD : a.num + b.num);
	}
	friend Modulo operator-(const Modulo& a, const Modulo& b)
	{
		return Modulo((a.num - b.num + MOD) >= MOD ? a.num - b.num : a.num - b.num + MOD);
	}
	friend Modulo operator*(const Modulo& a, const Modulo& b)
	{
		return Modulo(a.num * b.num % MOD);
	}
	friend Modulo operator/(const Modulo& a, const Modulo& b)
	{
		return Modulo(a.num * Inv(b.num) % MOD);
	}
	/*====================*/
	friend bool operator< (const Modulo& a, const Modulo& b)
	{
		return a.num < b.num;
	}
	friend bool operator==(const Modulo& a, const Modulo& b)
	{
		return a.num == b.num;
	}
	friend bool operator> (const Modulo& a, const Modulo& b)
	{
		return a.num > b.num;
	}
	friend bool operator<=(const Modulo& a, const Modulo& b)
	{
		return a.num <= b.num;
	}
	friend bool operator!=(const Modulo& a, const Modulo& b)
	{
		return a.num != b.num;
	}
	friend bool operator>=(const Modulo& a, const Modulo& b)
	{
		return a.num >= b.num;
	}
	/*====================*/
	void operator+=(const Modulo& x)
	{
		num = num + x.num; if (num >= MOD)num -= MOD;
	}
	void operator-=(const Modulo& x)
	{
		num = num - x.num + MOD; if (num >= MOD)num -= MOD;
	}
	void operator*=(const Modulo& x)
	{
		num = num * x.num % MOD;
	}
	void operator/=(const Modulo& x)
	{
		num = num * Inv(x.num) % MOD;
	}
	/*====================*/
	friend ostream& operator<<(ostream& output, Modulo integer)
	{
		output << integer.num; return output;
	}
	friend istream& operator>>(istream& input, Modulo& integer)
	{
		int temp; input >> temp; integer = (temp % MOD + MOD) % MOD; return input;
	}
};