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!)
*/
标签:__,std,1.0,K8He,i32,namespace,int,using
From: https://www.cnblogs.com/K8He/p/chat_20231013.html