Code
namespace User_Unauthorized {
/**
* @brief This is a header file for competitive programming.
* @author User-Unauthorized
* @version 1.0.0
* @date 2023-10-5
*/
typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
typedef std::vector<ValueMatrix> ValueCube;
typedef std::map<valueType, valueType> ValueMap;
typedef std::set<valueType> ValueSet;
typedef std::pair<valueType, valueType> ValuePair;
typedef std::vector<ValuePair> PairVector;
typedef std::vector<PairVector> PairMatrix;
typedef std::vector<PairMatrix> PairCube;
typedef std::map<ValuePair, valueType> PairMap;
typedef std::set<ValuePair> PairSet;
typedef std::vector<bool> bitset;
typedef std::vector<bitset> BitMatrix;
typedef std::vector<BitMatrix> BitCube;
typedef long double realType;
typedef std::vector<realType> RealVector;
typedef std::vector<RealVector> RealMatrix;
typedef std::vector<RealMatrix> RealCube;
typedef std::pair<realType, realType> RealPair;
typedef std::vector<RealPair> RealPairVector;
typedef std::vector<RealPairVector> RealPairMatrix;
typedef std::vector<RealPairMatrix> RealPairCube;
typedef std::mt19937 Engine;
typedef std::uniform_int_distribution<valueType> Distribution;
typedef unsigned long long hashType;
typedef std::vector<hashType> HashVector;
typedef std::vector<HashVector> HashMatrix;
typedef std::vector<HashMatrix> HashCube;
typedef std::map<hashType, valueType> HashMap;
typedef std::set<hashType> HashSet;
namespace ModOper {
/**
* @brief This is a set of functions for fast processing of operations under the meaning of taking modulus in competitive programming.
* @author User-Unauthorized
* @version 1.0.0
* @warning Please note that the parameter types of these functions must be integer types, otherwise a compilation error will occur.
* */
valueType MOD; // mod value
/**
* @brief This is a macro for whether to ensure that the parameters passed in are integers in the range [0, MOD), if it cannot be guaranteed, the value of this macro should be true, otherwise unexpected results may occur.
*/
#define ModOperSafeModOption false
/**
* @brief This function can increase the value of a by b.
* @tparam T1
* @tparam T2
* @tparam T3
* @param a
* @param b
* @param mod
*/
template<typename T1, typename T2, typename T3 = valueType>
void Inc(T1 &a, T2 b, const T3 &mod = MOD) {
#if ModOperSafeModOption
a %= mod;
b %= mod;
if (a < 0)
a += mod;
if (b < 0)
b += mod;
#endif // ModOperSafeModOption
a = a + b;
if (a >= mod)
a -= mod;
}
/**
* @brief This function can decrease the value of a by b.
* @tparam T1
* @tparam T2
* @tparam T3
* @param a
* @param b
* @param mod
*/
template<typename T1, typename T2, typename T3 = valueType>
void Dec(T1 &a, T2 b, const T3 &mod = MOD) {
#if ModOperSafeModOption
a %= mod;
b %= mod;
if (a < 0)
a += mod;
if (b < 0)
b += mod;
#endif // ModOperSafeModOption
a = a - b;
if (a < 0)
a += mod;
}
/**
* @brief This function can calculate the sum of a and b.
* @tparam T1
* @tparam T2
* @tparam T3
* @param a
* @param b
* @param mod
* @return T1
*/
template<typename T1, typename T2, typename T3 = valueType>
T1 sum(T1 a, T2 b, const T3 &mod = MOD) {
#if ModOperSafeModOption
a %= mod;
b %= mod;
if (a < 0)
a += mod;
if (b < 0)
b += mod;
#endif // ModOperSafeModOption
return a + b >= mod ? a + b - mod : a + b;
}
/**
* @brief This function can calculate the difference of a and b.
* @tparam T1
* @tparam T2
* @tparam T3
* @param a
* @param b
* @param mod
* @return T1
*/
template<typename T1, typename T2, typename T3 = valueType>
T1 sub(T1 a, T2 b, const T3 &mod = MOD) {
#if ModOperSafeModOption
a %= mod;
b %= mod;
if (a < 0)
a += mod;
if (b < 0)
b += mod;
#endif // ModOperSafeModOption
return a - b < 0 ? a - b + mod : a - b;
}
/**
* @brief This function can calculate the product of a and b.
* @tparam T1
* @tparam T2
* @tparam T3
* @param a
* @param b
* @param mod
* @return T1
*/
template<typename T1, typename T2, typename T3 = valueType>
T1 mul(T1 a, T2 b, const T3 &mod = MOD) {
#if ModOperSafeModOption
a %= mod;
b %= mod;
if (a < 0)
a += mod;
if (b < 0)
b += mod;
#endif // ModOperSafeModOption
return (long long) a * b % mod;
}
/**
* @brief This function can make the value of a multiply b.
* @tparam T1
* @tparam T2
* @tparam T3
* @param a
* @param b
* @param mod
* @return T1
*/
template<typename T1, typename T2, typename T3 = valueType>
void Mul(T1 &a, T2 b, const T3 &mod = MOD) {
#if ModOperSafeModOption
a %= mod;
b %= mod;
if (a < 0)
a += mod;
if (b < 0)
b += mod;
#endif // ModOperSafeModOption
a = (long long) a * b % mod;
}
/**
* @brief This function can calculate the b-th power of a, and the time complexity is log b.
* @tparam T1
* @tparam T2
* @tparam T3
* @param a
* @param b
* @param mod
* @return T1
*/
template<typename T1, typename T2, typename T3 = valueType>
T1 pow(T1 a, T2 b, const T3 &mod = MOD) {
#if ModOperSafeModOption
a %= mod;
b %= mod;
if (a < 0)
a += mod;
if (b < 0)
b += mod;
#endif // ModOperSafeModOption
T1 result = 1;
while (b > 0) {
if (b & 1)
Mul(result, a, mod);
Mul(a, a, mod);
b = b >> 1;
}
return result;
}
} // namespace ModOper
} // namespace User_Unauthorized