minmax_inclusion_exclusion.hpp¶

SECTIONMath INCLUDEnoya/minmax_inclusion_exclusion.hpp

给出扩展 min-max 容斥的系数；用于把第 \(k\) 小/大或顺序统计量表示成子集最值之和。

\[ \displaystyle (-1)^{s-k}\binom{s-1}{k-1} \]

Complexity: Time: O(n 2^n) coefficient construction/evaluation. Space: O(2^n).

Implementation¶

ReferenceSourceExpanded

当前头文件，省略 include guard；依赖见 #include。

/// @complexity Time: O(n 2^n) coefficient construction/evaluation.
/// Space: O(2^n).

#include <bit>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <vector>

namespace noya {

/// @brief Coefficients for extended min-max inclusion-exclusion:
/// (-1)^(s-k) C(s-1,k-1) for subset size s.
inline std::vector<std::int64_t>
minmax_inclusion_exclusion_coefficients(int n, int k) {
  assert(1 <= k && k <= n);
  std::vector<std::int64_t> res(n + 1);
  std::int64_t com = 1;
  for (int sz = k; sz <= n; sz++) {
    if (sz > k) {
      com = com * (sz - 1) / (sz - k);
    }
    res[sz] = ((sz - k) & 1) ? -com : com;
  }
  return res;
}

namespace minmax_inclusion_exclusion_internal {

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 = minmax_inclusion_exclusion_coefficients(n, k);
  T res{};
  for (std::size_t mas = 1; mas < ext.size(); mas++) {
    res += ext[mas] * static_cast<T>(cf[std::popcount(mas)]);
  }
  return res;
}

} // namespace minmax_inclusion_exclusion_internal

/// @brief Recover the k-th largest of n elements from the minimum of every
/// nonempty subset; k is one-indexed.
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.
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

#ifndef NOYA_MINMAX_INCLUSION_EXCLUSION_HPP
#define NOYA_MINMAX_INCLUSION_EXCLUSION_HPP 1

/// @complexity Time: O(n 2^n) coefficient construction/evaluation.
/// Space: O(2^n).

#include <bit>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <vector>

namespace noya {

/// @brief Coefficients for extended min-max inclusion-exclusion:
/// (-1)^(s-k) C(s-1,k-1) for subset size s.
inline std::vector<std::int64_t>
minmax_inclusion_exclusion_coefficients(int n, int k) {
  assert(1 <= k && k <= n);
  std::vector<std::int64_t> res(n + 1);
  std::int64_t com = 1;
  for (int sz = k; sz <= n; sz++) {
    if (sz > k) {
      com = com * (sz - 1) / (sz - k);
    }
    res[sz] = ((sz - k) & 1) ? -com : com;
  }
  return res;
}

namespace minmax_inclusion_exclusion_internal {

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 = minmax_inclusion_exclusion_coefficients(n, k);
  T res{};
  for (std::size_t mas = 1; mas < ext.size(); mas++) {
    res += ext[mas] * static_cast<T>(cf[std::popcount(mas)]);
  }
  return res;
}

} // namespace minmax_inclusion_exclusion_internal

/// @brief Recover the k-th largest of n elements from the minimum of every
/// nonempty subset; k is one-indexed.
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.
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

#include <bit>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <vector>

/// @complexity Time: O(n 2^n) coefficient construction/evaluation.
/// Space: O(2^n).

namespace noya {

/// @brief Coefficients for extended min-max inclusion-exclusion:
/// (-1)^(s-k) C(s-1,k-1) for subset size s.
inline std::vector<std::int64_t>
minmax_inclusion_exclusion_coefficients(int n, int k) {
  assert(1 <= k && k <= n);
  std::vector<std::int64_t> res(n + 1);
  std::int64_t com = 1;
  for (int sz = k; sz <= n; sz++) {
    if (sz > k) {
      com = com * (sz - 1) / (sz - k);
    }
    res[sz] = ((sz - k) & 1) ? -com : com;
  }
  return res;
}

namespace minmax_inclusion_exclusion_internal {

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 = minmax_inclusion_exclusion_coefficients(n, k);
  T res{};
  for (std::size_t mas = 1; mas < ext.size(); mas++) {
    res += ext[mas] * static_cast<T>(cf[std::popcount(mas)]);
  }
  return res;
}

} // namespace minmax_inclusion_exclusion_internal

/// @brief Recover the k-th largest of n elements from the minimum of every
/// nonempty subset; k is one-indexed.
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.
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