prime_binomial_table.hpp¶
在运行时给定素数模 \(p\)，预处理 \(p\) 以下范围的阶乘后快速查询组合数。
\[
\displaystyle \binom{n}{k} \equiv n!/(k!(n-k)!) \pmod p
\]
Complexity: Time: O(N + log p) preprocessing and O(1) per query. Space: O(N).
AC 记录：binomial_coefficient_prime_mod。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(N + log p) preprocessing and O(1) per query.
/// Space: O(N).
#include <cassert>
#include <cstdint>
#include <vector>
namespace noya {
/// @brief Binomial coefficients modulo a runtime prime p for arguments below
/// p. Store factorials and inverse factorials through N; Fermat inversion of
/// N! followed by a backward sweep obtains every inverse using one power.
class prime_binomial_table {
public:
prime_binomial_table() = default;
prime_binomial_table(int mx, std::uint32_t p) { build(mx, p); }
void build(int mx, std::uint32_t p) {
assert(mx >= 0 && std::uint64_t(mx) < p);
md = p;
fac.resize(mx + 1);
ifc.resize(mx + 1);
fac[0] = 1 % p;
for (int i = 1; i <= mx; i++) {
fac[i] = multiply(fac[i - 1], i);
}
ifc[mx] = power(fac[mx], p - 2);
for (int i = mx; i > 0; i--) {
ifc[i - 1] = multiply(ifc[i], i);
}
}
std::uint32_t choose(int n, int k) const {
if (k < 0 || k > n) {
return 0;
}
assert(n < int(fac.size()));
return multiply(fac[n], multiply(ifc[k], ifc[n - k]));
}
private:
std::uint32_t md = 1;
std::vector<std::uint32_t> fac;
std::vector<std::uint32_t> ifc;
std::uint32_t multiply(std::uint64_t a, std::uint64_t b) const {
return std::uint32_t(a * b % md);
}
std::uint32_t power(std::uint32_t val, std::uint64_t exp) const {
std::uint32_t res = 1 % md;
while (exp > 0) {
if (exp & 1) {
res = multiply(res, val);
}
val = multiply(val, val);
exp >>= 1;
}
return res;
}
};
} // namespace noya
#ifndef NOYA_PRIME_BINOMIAL_TABLE_HPP
#define NOYA_PRIME_BINOMIAL_TABLE_HPP 1
/// @complexity Time: O(N + log p) preprocessing and O(1) per query.
/// Space: O(N).
#include <cassert>
#include <cstdint>
#include <vector>
namespace noya {
/// @brief Binomial coefficients modulo a runtime prime p for arguments below
/// p. Store factorials and inverse factorials through N; Fermat inversion of
/// N! followed by a backward sweep obtains every inverse using one power.
class prime_binomial_table {
public:
prime_binomial_table() = default;
prime_binomial_table(int mx, std::uint32_t p) { build(mx, p); }
void build(int mx, std::uint32_t p) {
assert(mx >= 0 && std::uint64_t(mx) < p);
md = p;
fac.resize(mx + 1);
ifc.resize(mx + 1);
fac[0] = 1 % p;
for (int i = 1; i <= mx; i++) {
fac[i] = multiply(fac[i - 1], i);
}
ifc[mx] = power(fac[mx], p - 2);
for (int i = mx; i > 0; i--) {
ifc[i - 1] = multiply(ifc[i], i);
}
}
std::uint32_t choose(int n, int k) const {
if (k < 0 || k > n) {
return 0;
}
assert(n < int(fac.size()));
return multiply(fac[n], multiply(ifc[k], ifc[n - k]));
}
private:
std::uint32_t md = 1;
std::vector<std::uint32_t> fac;
std::vector<std::uint32_t> ifc;
std::uint32_t multiply(std::uint64_t a, std::uint64_t b) const {
return std::uint32_t(a * b % md);
}
std::uint32_t power(std::uint32_t val, std::uint64_t exp) const {
std::uint32_t res = 1 % md;
while (exp > 0) {
if (exp & 1) {
res = multiply(res, val);
}
val = multiply(val, val);
exp >>= 1;
}
return res;
}
};
} // namespace noya
#endif // NOYA_PRIME_BINOMIAL_TABLE_HPP
#include <cassert>
#include <cstdint>
#include <vector>
/// @complexity Time: O(N + log p) preprocessing and O(1) per query.
/// Space: O(N).
namespace noya {
/// @brief Binomial coefficients modulo a runtime prime p for arguments below
/// p. Store factorials and inverse factorials through N; Fermat inversion of
/// N! followed by a backward sweep obtains every inverse using one power.
class prime_binomial_table {
public:
prime_binomial_table() = default;
prime_binomial_table(int mx, std::uint32_t p) { build(mx, p); }
void build(int mx, std::uint32_t p) {
assert(mx >= 0 && std::uint64_t(mx) < p);
md = p;
fac.resize(mx + 1);
ifc.resize(mx + 1);
fac[0] = 1 % p;
for (int i = 1; i <= mx; i++) {
fac[i] = multiply(fac[i - 1], i);
}
ifc[mx] = power(fac[mx], p - 2);
for (int i = mx; i > 0; i--) {
ifc[i - 1] = multiply(ifc[i], i);
}
}
std::uint32_t choose(int n, int k) const {
if (k < 0 || k > n) {
return 0;
}
assert(n < int(fac.size()));
return multiply(fac[n], multiply(ifc[k], ifc[n - k]));
}
private:
std::uint32_t md = 1;
std::vector<std::uint32_t> fac;
std::vector<std::uint32_t> ifc;
std::uint32_t multiply(std::uint64_t a, std::uint64_t b) const {
return std::uint32_t(a * b % md);
}
std::uint32_t power(std::uint32_t val, std::uint64_t exp) const {
std::uint32_t res = 1 % md;
while (exp > 0) {
if (exp & 1) {
res = multiply(res, val);
}
val = multiply(val, val);
exp >>= 1;
}
return res;
}
};
} // namespace noya