This documentation is automatically generated by competitive-verifier/competitive-verifier
#include "cp-algo/math/combinatorics.hpp"
#ifndef CP_ALGO_MATH_COMBINATORICS_HPP
#define CP_ALGO_MATH_COMBINATORICS_HPP
#include "common.hpp"
#include <cassert>
namespace cp_algo::math {
// fact/rfact/small_inv are caching
// Beware of usage with dynamic mod
template<typename T>
T fact(int n) {
static std::vector<T> F(maxn);
static bool init = false;
if(!init) {
F[0] = T(1);
for(int i = 1; i < maxn; i++) {
F[i] = F[i - 1] * T(i);
}
init = true;
}
return F[n];
}
// Only works for modint types
template<typename T>
T rfact(int n) {
static std::vector<T> F(maxn);
static bool init = false;
if(!init) {
int t = std::min<int64_t>(T::mod(), maxn) - 1;
F[t] = T(1) / fact<T>(t);
for(int i = t - 1; i >= 0; i--) {
F[i] = F[i + 1] * T(i + 1);
}
init = true;
}
return F[n];
}
template<typename T>
T small_inv(int n) {
static std::vector<T> F(maxn);
static bool init = false;
if(!init) {
for(int i = 1; i < maxn; i++) {
F[i] = rfact<T>(i) * fact<T>(i - 1);
}
init = true;
}
return F[n];
}
template<typename T>
T binom_large(T n, int r) {
assert(r < maxn);
T ans = 1;
for(int i = 0; i < r; i++) {
ans = ans * T(n - i) * small_inv<T>(i + 1);
}
return ans;
}
template<typename T>
T binom(int n, int r) {
if(r < 0 || r > n) {
return T(0);
} else if(n >= maxn) {
return binom_large(T(n), r);
} else {
return fact<T>(n) * rfact<T>(r) * rfact<T>(n - r);
}
}
}
#endif // CP_ALGO_MATH_COMBINATORICS_HPP
#line 1 "cp-algo/math/combinatorics.hpp"
#line 1 "cp-algo/math/common.hpp"
#include <functional>
#include <cstdint>
namespace cp_algo::math {
#ifdef CP_ALGO_MAXN
const int maxn = CP_ALGO_MAXN;
#else
const int maxn = 1 << 19;
#endif
const int magic = 64; // threshold for sizes to run the naive algo
auto bpow(auto const& x, auto n, auto const& one, auto op) {
if(n == 0) {
return one;
} else {
auto t = bpow(x, n / 2, one, op);
t = op(t, t);
if(n % 2) {
t = op(t, x);
}
return t;
}
}
auto bpow(auto x, auto n, auto ans) {
return bpow(x, n, ans, std::multiplies{});
}
template<typename T>
T bpow(T const& x, auto n) {
return bpow(x, n, T(1));
}
}
#line 4 "cp-algo/math/combinatorics.hpp"
#include <cassert>
namespace cp_algo::math {
// fact/rfact/small_inv are caching
// Beware of usage with dynamic mod
template<typename T>
T fact(int n) {
static std::vector<T> F(maxn);
static bool init = false;
if(!init) {
F[0] = T(1);
for(int i = 1; i < maxn; i++) {
F[i] = F[i - 1] * T(i);
}
init = true;
}
return F[n];
}
// Only works for modint types
template<typename T>
T rfact(int n) {
static std::vector<T> F(maxn);
static bool init = false;
if(!init) {
int t = std::min<int64_t>(T::mod(), maxn) - 1;
F[t] = T(1) / fact<T>(t);
for(int i = t - 1; i >= 0; i--) {
F[i] = F[i + 1] * T(i + 1);
}
init = true;
}
return F[n];
}
template<typename T>
T small_inv(int n) {
static std::vector<T> F(maxn);
static bool init = false;
if(!init) {
for(int i = 1; i < maxn; i++) {
F[i] = rfact<T>(i) * fact<T>(i - 1);
}
init = true;
}
return F[n];
}
template<typename T>
T binom_large(T n, int r) {
assert(r < maxn);
T ans = 1;
for(int i = 0; i < r; i++) {
ans = ans * T(n - i) * small_inv<T>(i + 1);
}
return ans;
}
template<typename T>
T binom(int n, int r) {
if(r < 0 || r > n) {
return T(0);
} else if(n >= maxn) {
return binom_large(T(n), r);
} else {
return fact<T>(n) * rfact<T>(r) * rfact<T>(n - r);
}
}
}