binomial.hpp¶

#include "noya/binomial.hpp"

SourceExpanded

#ifndef NOYA_BINOMIAL_HPP
#define NOYA_BINOMIAL_HPP 1

#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, ifac;
  binom() {}
  binom(int n) { prepare(n); }

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

    for (int i = int(fac.size()); i <= n; i++) {
      fac.push_back(fac[i - 1] * i);
      ifac.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(ifac.size()))
      prepare(n * 2);
    return ifac[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>

namespace noya {
/// @brief Precomputed binomial coefficient table over a modular type T.
template <class T> struct binom {
  std::vector<T> fac, ifac;
  binom() {}
  binom(int n) { prepare(n); }

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

    for (int i = int(fac.size()); i <= n; i++) {
      fac.push_back(fac[i - 1] * i);
      ifac.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(ifac.size()))
      prepare(n * 2);
    return ifac[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);
  }
};
}