minmax_inclusion_exclusion.hpp¶
给出扩展 min-max 容斥的系数；用于把第 \(k\) 小/大或顺序统计量表示成子集最值之和。
\[
\displaystyle (-1)^{s-k}\binom{s-1}{k-1}
\]
Complexity: Time: \(O(n)\) coefficient construction; \(O(2^{n})\) scalar operations to evaluate a subset table for \(n\) elements. Space: \(O(n)\) auxiliary storage, excluding the supplied table of size \(2^{n}\).
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n) coefficient construction; O(2^n) scalar operations
/// to evaluate a subset table for n elements. Space: O(n) auxiliary storage,
/// excluding the supplied table of size 2^n.
#include <bit>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <vector>
namespace noya {
namespace minmax_inclusion_exclusion_internal {
template <class T> std::vector<T> coefficients(int n, int k) {
assert(1 <= k && k <= n);
std::vector<T> res(n + 1);
std::int64_t com = 1;
for (int sz = k; sz <= n; sz++) {
if (sz > k) {
__int128 next = static_cast<__int128>(com) * (sz - 1) / (sz - k);
assert(next <= std::numeric_limits<std::int64_t>::max());
com = std::int64_t(next);
}
res[sz] = static_cast<T>(((sz - k) & 1) ? -com : com);
}
return res;
}
template <class T> T transform(const std::vector<T> &ext, int k) {
assert(ext.size() >= 2 && std::has_single_bit(ext.size()));
int n = std::countr_zero(ext.size());
auto cf = coefficients<T>(n, k);
T res{};
for (std::size_t mas = 1; mas < ext.size(); mas++) {
res += ext[mas] * cf[std::popcount(mas)];
}
return res;
}
} // namespace minmax_inclusion_exclusion_internal
/// @brief Coefficients (-1)^(s-k) C(s-1,k-1) for subset size s.
/// Requires 1 <= k <= n and C(n-1,k-1) to fit int64_t.
inline std::vector<std::int64_t>
minmax_inclusion_exclusion_coefficients(int n, int k) {
return minmax_inclusion_exclusion_internal::coefficients<std::int64_t>(n, k);
}
/// @brief Recover the k-th largest of n elements from the minimum of every
/// nonempty subset; k is one-indexed.
/// With built-in signed integers, products and partial sums must fit T.
template <class T>
T kth_largest_from_subset_minima(const std::vector<T> &mn, int k) {
return minmax_inclusion_exclusion_internal::transform(mn, k);
}
/// @brief Recover the k-th smallest of n elements from the maximum of every
/// nonempty subset; k is one-indexed.
/// With built-in signed integers, products and partial sums must fit T.
template <class T>
T kth_smallest_from_subset_maxima(const std::vector<T> &mx, int k) {
return minmax_inclusion_exclusion_internal::transform(mx, k);
}
} // namespace noya
// NOYA_MINMAX_INCLUSION_EXCLUSION_HPP
#ifndef NOYA_MINMAX_INCLUSION_EXCLUSION_HPP
#define NOYA_MINMAX_INCLUSION_EXCLUSION_HPP 1
/// @complexity Time: O(n) coefficient construction; O(2^n) scalar operations
/// to evaluate a subset table for n elements. Space: O(n) auxiliary storage,
/// excluding the supplied table of size 2^n.
#include <bit>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <vector>
namespace noya {
namespace minmax_inclusion_exclusion_internal {
template <class T> std::vector<T> coefficients(int n, int k) {
assert(1 <= k && k <= n);
std::vector<T> res(n + 1);
std::int64_t com = 1;
for (int sz = k; sz <= n; sz++) {
if (sz > k) {
__int128 next = static_cast<__int128>(com) * (sz - 1) / (sz - k);
assert(next <= std::numeric_limits<std::int64_t>::max());
com = std::int64_t(next);
}
res[sz] = static_cast<T>(((sz - k) & 1) ? -com : com);
}
return res;
}
template <class T> T transform(const std::vector<T> &ext, int k) {
assert(ext.size() >= 2 && std::has_single_bit(ext.size()));
int n = std::countr_zero(ext.size());
auto cf = coefficients<T>(n, k);
T res{};
for (std::size_t mas = 1; mas < ext.size(); mas++) {
res += ext[mas] * cf[std::popcount(mas)];
}
return res;
}
} // namespace minmax_inclusion_exclusion_internal
/// @brief Coefficients (-1)^(s-k) C(s-1,k-1) for subset size s.
/// Requires 1 <= k <= n and C(n-1,k-1) to fit int64_t.
inline std::vector<std::int64_t>
minmax_inclusion_exclusion_coefficients(int n, int k) {
return minmax_inclusion_exclusion_internal::coefficients<std::int64_t>(n, k);
}
/// @brief Recover the k-th largest of n elements from the minimum of every
/// nonempty subset; k is one-indexed.
/// With built-in signed integers, products and partial sums must fit T.
template <class T>
T kth_largest_from_subset_minima(const std::vector<T> &mn, int k) {
return minmax_inclusion_exclusion_internal::transform(mn, k);
}
/// @brief Recover the k-th smallest of n elements from the maximum of every
/// nonempty subset; k is one-indexed.
/// With built-in signed integers, products and partial sums must fit T.
template <class T>
T kth_smallest_from_subset_maxima(const std::vector<T> &mx, int k) {
return minmax_inclusion_exclusion_internal::transform(mx, k);
}
} // namespace noya
#endif // NOYA_MINMAX_INCLUSION_EXCLUSION_HPP
/// @complexity Time: O(n) coefficient construction; O(2^n) scalar operations
/// to evaluate a subset table for n elements. Space: O(n) auxiliary storage,
/// excluding the supplied table of size 2^n.
#include <bit>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <vector>
namespace noya {
namespace minmax_inclusion_exclusion_internal {
template <class T> std::vector<T> coefficients(int n, int k) {
assert(1 <= k && k <= n);
std::vector<T> res(n + 1);
std::int64_t com = 1;
for (int sz = k; sz <= n; sz++) {
if (sz > k) {
__int128 next = static_cast<__int128>(com) * (sz - 1) / (sz - k);
assert(next <= std::numeric_limits<std::int64_t>::max());
com = std::int64_t(next);
}
res[sz] = static_cast<T>(((sz - k) & 1) ? -com : com);
}
return res;
}
template <class T> T transform(const std::vector<T> &ext, int k) {
assert(ext.size() >= 2 && std::has_single_bit(ext.size()));
int n = std::countr_zero(ext.size());
auto cf = coefficients<T>(n, k);
T res{};
for (std::size_t mas = 1; mas < ext.size(); mas++) {
res += ext[mas] * cf[std::popcount(mas)];
}
return res;
}
} // namespace minmax_inclusion_exclusion_internal
/// @brief Coefficients (-1)^(s-k) C(s-1,k-1) for subset size s.
/// Requires 1 <= k <= n and C(n-1,k-1) to fit int64_t.
inline std::vector<std::int64_t>
minmax_inclusion_exclusion_coefficients(int n, int k) {
return minmax_inclusion_exclusion_internal::coefficients<std::int64_t>(n, k);
}
/// @brief Recover the k-th largest of n elements from the minimum of every
/// nonempty subset; k is one-indexed.
/// With built-in signed integers, products and partial sums must fit T.
template <class T>
T kth_largest_from_subset_minima(const std::vector<T> &mn, int k) {
return minmax_inclusion_exclusion_internal::transform(mn, k);
}
/// @brief Recover the k-th smallest of n elements from the maximum of every
/// nonempty subset; k is one-indexed.
/// With built-in signed integers, products and partial sums must fit T.
template <class T>
T kth_smallest_from_subset_maxima(const std::vector<T> &mx, int k) {
return minmax_inclusion_exclusion_internal::transform(mx, k);
}
} // namespace noya
// NOYA_MINMAX_INCLUSION_EXCLUSION_HPP