binomial.hpp¶

SECTIONMath INCLUDEnoya/math/binomial.hpp

预处理阶乘与逆阶乘，快速计算组合数、排列数和多重组合数；适合模数为素数且参数规模可预处理。

\[ \displaystyle \binom{n}{k}=\frac{n!}{k!(n-k)!} \]

Complexity: Time: \(O(n + I)\) preprocessing, \(O(1)\) cached queries. Automatic growth to \(n\) totals \(O(n + I \log n)\), with inversion cost \(I\). Space: \(O(n)\).

跳到代码 · GitHub ↗

Implementation¶

ReferenceSourceExpanded

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

/// @complexity Time: O(n + I) preprocessing, O(1) cached queries.
/// Automatic growth to n totals O(n + I log n), with inversion cost I.
/// Space: O(n).

#include <vector>
#include <limits>
#include <cassert>

namespace noya {
/// @brief Factorials and inverse factorials over a fixed modular type T.
/// All prepared factorials must be invertible; for a prime p, use indices < p.
template <class T> struct binom {
  std::vector<T> fac, ifc;
  binom() {}
  binom(int n) { prepare(n); }

  /// @brief Precompute factorials and inverse factorials up to n.
  void prepare(int n) {
    if (fac.empty()) {
      fac = {1};
      ifc = {1};
    }

    int first = fac.size();
    if (n < first) return;
    assert(n < std::numeric_limits<int>::max());
    fac.resize(n + 1, T(1));
    ifc.resize(n + 1, T(1));
    for (int i = first; i <= n; ++i) fac[i] = fac[i - 1] * i;
    ifc[n] = fac[n].inv();
    for (int i = n; i > first; --i) ifc[i - 1] = ifc[i] * i;
  }

  /// @brief Return n! (mod p).
  T fact(int n) {
    assert(n >= 0);
    if (n >= int(fac.size())) ensure(n);
    return fac[n];
  }

  /// @brief Return (n!)^{-1} (mod p).
  T ifact(int n) {
    assert(n >= 0);
    if (n >= int(ifc.size())) ensure(n);
    return ifc[n];
  }

  /// @brief Return the binomial coefficient C(n, m).
  T C(int n, int m) {
    if (!(0 <= m && m <= n))
      return 0;
    T value = fact(n);
    return value * ifc[m] * ifc[n - m];
  }

private:
  void ensure(int n) {
    assert(0 <= n && n < std::numeric_limits<int>::max());
    if (n < int(fac.size())) return;
    int target = n <= std::numeric_limits<int>::max() / 2 ? n * 2 : n;
    if constexpr (requires { T::mod(); }) {
      if (T::mod() <= target) target = int(T::mod()) - 1;
    }
    assert(n <= target);
    prepare(target);
  }

};
}


 // NOYA_BINOMIAL_HPP

#ifndef NOYA_BINOMIAL_HPP
#define NOYA_BINOMIAL_HPP 1

/// @complexity Time: O(n + I) preprocessing, O(1) cached queries.
/// Automatic growth to n totals O(n + I log n), with inversion cost I.
/// Space: O(n).

#include <vector>
#include <limits>
#include <cassert>

namespace noya {
/// @brief Factorials and inverse factorials over a fixed modular type T.
/// All prepared factorials must be invertible; for a prime p, use indices < p.
template <class T> struct binom {
  std::vector<T> fac, ifc;
  binom() {}
  binom(int n) { prepare(n); }

  /// @brief Precompute factorials and inverse factorials up to n.
  void prepare(int n) {
    if (fac.empty()) {
      fac = {1};
      ifc = {1};
    }

    int first = fac.size();
    if (n < first) return;
    assert(n < std::numeric_limits<int>::max());
    fac.resize(n + 1, T(1));
    ifc.resize(n + 1, T(1));
    for (int i = first; i <= n; ++i) fac[i] = fac[i - 1] * i;
    ifc[n] = fac[n].inv();
    for (int i = n; i > first; --i) ifc[i - 1] = ifc[i] * i;
  }

  /// @brief Return n! (mod p).
  T fact(int n) {
    assert(n >= 0);
    if (n >= int(fac.size())) ensure(n);
    return fac[n];
  }

  /// @brief Return (n!)^{-1} (mod p).
  T ifact(int n) {
    assert(n >= 0);
    if (n >= int(ifc.size())) ensure(n);
    return ifc[n];
  }

  /// @brief Return the binomial coefficient C(n, m).
  T C(int n, int m) {
    if (!(0 <= m && m <= n))
      return 0;
    T value = fact(n);
    return value * ifc[m] * ifc[n - m];
  }

private:
  void ensure(int n) {
    assert(0 <= n && n < std::numeric_limits<int>::max());
    if (n < int(fac.size())) return;
    int target = n <= std::numeric_limits<int>::max() / 2 ? n * 2 : n;
    if constexpr (requires { T::mod(); }) {
      if (T::mod() <= target) target = int(T::mod()) - 1;
    }
    assert(n <= target);
    prepare(target);
  }

};
}


#endif // NOYA_BINOMIAL_HPP

/// @complexity Time: O(n + I) preprocessing, O(1) cached queries.
/// Automatic growth to n totals O(n + I log n), with inversion cost I.
/// Space: O(n).

#include <vector>
#include <limits>
#include <cassert>

namespace noya {
/// @brief Factorials and inverse factorials over a fixed modular type T.
/// All prepared factorials must be invertible; for a prime p, use indices < p.
template <class T> struct binom {
  std::vector<T> fac, ifc;
  binom() {}
  binom(int n) { prepare(n); }

  /// @brief Precompute factorials and inverse factorials up to n.
  void prepare(int n) {
    if (fac.empty()) {
      fac = {1};
      ifc = {1};
    }

    int first = fac.size();
    if (n < first) return;
    assert(n < std::numeric_limits<int>::max());
    fac.resize(n + 1, T(1));
    ifc.resize(n + 1, T(1));
    for (int i = first; i <= n; ++i) fac[i] = fac[i - 1] * i;
    ifc[n] = fac[n].inv();
    for (int i = n; i > first; --i) ifc[i - 1] = ifc[i] * i;
  }

  /// @brief Return n! (mod p).
  T fact(int n) {
    assert(n >= 0);
    if (n >= int(fac.size())) ensure(n);
    return fac[n];
  }

  /// @brief Return (n!)^{-1} (mod p).
  T ifact(int n) {
    assert(n >= 0);
    if (n >= int(ifc.size())) ensure(n);
    return ifc[n];
  }

  /// @brief Return the binomial coefficient C(n, m).
  T C(int n, int m) {
    if (!(0 <= m && m <= n))
      return 0;
    T value = fact(n);
    return value * ifc[m] * ifc[n - m];
  }

private:
  void ensure(int n) {
    assert(0 <= n && n < std::numeric_limits<int>::max());
    if (n < int(fac.size())) return;
    int target = n <= std::numeric_limits<int>::max() / 2 ? n * 2 : n;
    if constexpr (requires { T::mod(); }) {
      if (T::mod() <= target) target = int(T::mod()) - 1;
    }
    assert(n <= target);
    prepare(target);
  }

};
}

 // NOYA_BINOMIAL_HPP