526互联

「闲话随笔」 C++ namespace K8He-Math version -1.0.0 is officially released!

发布时间 2023-10-13 19:57:24作者: K8He

C++ namespace K8He-Math version -1.0.0 is officially released!

写着玩的，不清楚是否有实用价值，看个乐就行，别 D .

有 Bug 可以自己调（

怎么用感觉比较好看出来 .

namespace MATH {
	namespace Type {
		using i32 = int;
		using i64 = long long;
		using u32 = std::uint32_t;
		using u64 = std::uint64_t;
		using vi32 = std::vector <i32>;
		using vu32 = std::vector <u32>;
		using vi64 = std::vector <i64>;
		using vu64 = std::vector <u64>;
		using pr32 = std::pair <i32, i32>;
		using pr64 = std::pair <i64, i64>;
	} // namespace Type
	using namespace Type;
	namespace Setting {
		constexpr i32 P = 998244353;
		constexpr i32 infi32 = 1 << 30;
		constexpr u32 infu32 = 1 << 31;
		constexpr i64 infi64 = 1ll << 60;
		constexpr u64 infu64 = 1ll << 63;
	} // namespace Setting
	using namespace Setting;
	i32 fpow (i32 a, i32 b, i32 ans = 1) {
		for (b += (b < 0) * (P - 1); b; a = 1ll * a * a % P, b >>= 1)
			if (b & 1) ans = 1ll * ans * a % P;
		return ans;
	} // This is fast pow. You can change the initial value.
	template<int a, const int B = 65535, const int mod = P>class LightPow {
	private:
		u32 __pow[2][B + 1];
	public:
		LightPow () {
			__pow[0][0] = 1, __pow[0][1] = a;
			for (int i = 2; i <= B; ++i) __pow[0][i] = 1ll * __pow[0][i - 1] * __pow[0][1] % P;
			__pow[1][0] = 1, __pow[1][1] = 1ll * __pow[0][B] * __pow[0][1] % P;
			for (int i = 2; i <= B; ++i) __pow[1][i] = 1ll * __pow[1][i - 1] * __pow[1][1] % P;
			return;
		}
		inline int gpow (int b) { return 1ll * __pow[0][b & B] * __pow[1][b >> 16] % P; }
	}; // O(B)-O(1) calculate a^b.
	namespace binom {
		vu32 __fac ({ 1, 1 }), __inv ({ 0, 1 }), __invf ({ 1, 1 });
		inline void __prep (i32 x) {
			static i32 i = 2;
			if (i < x) {
				for (__fac.resize (x), __inv.resize (x), __invf.resize (x); i < x; ++i) {
					__fac[i] = 1ull * __fac[i - 1] * i % P;
					__inv[i] = 1ull * (P - P / i) * __inv[P % i] % P;
					__invf[i] = 1ull * __invf[i - 1] * __inv[i] % P;
				}
			}
			return;
		} inline i32 gfac (i32 x) {
			return __prep (x + 1), __fac[x];
		} inline i32 ginv (i32 x) {
			return __prep (x + 1), __inv[x];
		} inline i32 ginvf (i32 x) {
			return __prep (x + 1), __invf[x];
		} inline i32 C (i32 n, i32 m) {
			return 1ll * gfac (n) * ginvf (n - m) % P * ginvf (m) % P;
		}
	} // namespace binom
	using binom::gfac, binom::ginv, binom::ginvf, binom::C;
	// Real time expansion, you don't need to call preprocessing functions!
	namespace LinearSieve {
		vu32 __prime, __low;
		std::vector <bool> __not_a_prime;
		inline vu32 SievePrime (int n) {
			std::vector<bool> ().swap (__not_a_prime);
			__not_a_prime = (std::vector <bool>)(n + 1, false);
			for (int i = 2; i <= n; ++i) {
				if (!__not_a_prime[i]) __prime.emplace_back (i);
				for (auto j : __prime) {
					if (i * j > n) break;
					__not_a_prime[i * j] = true;
					if (!(i % j)) break;
				}
			}
			return __prime;
		} // Obtain a vector for storing prime numbers.
		inline vi32 SieveMultiF (int n, int fp (int x), int fpk (int x)) {
			vi32 ans (n + 1, 0);
			__low = vu32 (n + 1, 0);
			__not_a_prime = (std::vector <bool>)(n + 1, false);
			for (int i = 2; i <= n; ++i) {
				if (!__not_a_prime[i]) {
					__prime.emplace_back (i);
					ans[i] = fp (i), __low[i] = i;
				}
				for (auto j : __prime) {
					if (i * j > n) break;
					__not_a_prime[i * j] = true;
					if (!(i % j)) {
						__low[i * j] = __low[i] * j;
						ans[i * j] = 1ll * fpk (__low[i * j]) * ans[i / __low[i]] % P;
						break;
					}
					ans[i] = 1ll * ans[i] * ans[j] % P, __low[i] = j;
				}
			}
			return ans;
		} // Linear sieve out product function f(x). You need to pass in two functions : f (x) (x \in P) and f (x^k) (x \in P, k).
		// But I think this function is very useless and cerebral palsy, why don't you write it yourself?
	} // namespace LinearSieve
	using LinearSieve::SievePrime, LinearSieve::SieveMultiF;
} // namespace MATH
/*
If I have time, I will add the following features, but I think it's too unlikely that I will have time.

TODO:

- exgcd
- CRT
- exCRT
- ~~Lucas~~(Go away, write it yourself)
- ~~exLucas~~(I don't want to touch this thing again in my life!)

*/