binomial.hpp

SECTIONMath INCLUDEnoya/binomial.hpp

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

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

Complexity: Time: O(n) preprocessing and O(1) per factorial/binomial query. Space: O(n).

跳到代码 · GitHub ↗

Implementation

ReferenceSourceExpanded

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

/// @complexity Time: O(n) preprocessing and O(1) per factorial/binomial query.
/// Space: O(n).

#include <vector>
#include <cassert>

namespace noya {
/// @brief Precomputed binomial coefficient table over a modular type T.
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};
    }

    for (int i = int(fac.size()); i <= n; i++) {
      fac.push_back(fac[i - 1] * i);
      ifc.push_back(fac[i].inv());
    }
  }

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

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

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

#ifndef NOYA_BINOMIAL_HPP
#define NOYA_BINOMIAL_HPP 1

/// @complexity Time: O(n) preprocessing and O(1) per factorial/binomial query.
/// Space: O(n).

#include <vector>
#include <cassert>

namespace noya {
/// @brief Precomputed binomial coefficient table over a modular type T.
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};
    }

    for (int i = int(fac.size()); i <= n; i++) {
      fac.push_back(fac[i - 1] * i);
      ifc.push_back(fac[i].inv());
    }
  }

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

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

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


#endif // NOYA_BINOMIAL_HPP

#include <cassert>
#include <vector>

/// @complexity Time: O(n) preprocessing and O(1) per factorial/binomial query.
/// Space: O(n).

namespace noya {
/// @brief Precomputed binomial coefficient table over a modular type T.
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};
    }

    for (int i = int(fac.size()); i <= n; i++) {
      fac.push_back(fac[i - 1] * i);
      ifc.push_back(fac[i].inv());
    }
  }

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

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

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