Factorial(階乗) (math/combinatorics/factorial.hpp)

• View this file on GitHub
• Last update: 2024-04-27 01:27:28+09:00
• Include: #include "math/combinatorics/factorial.hpp"

Depends on

• Enumeration(組み合わせ) (math/combinatorics/enumeration.hpp)
• Sample Point Shift(標本点シフト) (math/combinatorics/sample-point-shift.hpp)

Verified with

• test/verify/yukicoder-502.test.cpp

Code

#include "sample-point-shift.hpp"

/**
 * @brief Factorial(階乗)
 */
template <typename Mint, typename F>
Mint factorial(int64_t n, const F& multiply) {
  if (n <= 1) return 1;
  if (n >= Mint::mod()) return 0;
  int64_t v = 1;
  while (v * v < n) v *= 2;
  Mint iv = Mint(1) / v;
  vector<Mint> G{1, v + 1};
  for (int64_t d = 1; d != v; d <<= 1) {
    vector<Mint> G1 = sample_point_shift(G, Mint(d) * iv, multiply);
    vector<Mint> G2 = sample_point_shift(G, Mint(d * v + v) * iv, multiply);
    vector<Mint> G3 = sample_point_shift(G, Mint(d * v + d + v) * iv, multiply);
    for (int i = 0; i <= d; i++) G[i] *= G1[i], G2[i] *= G3[i];
    copy(begin(G2), end(G2) - 1, back_inserter(G));
  }
  Mint res = 1;
  int64_t i = 0;
  while (i + v <= n) res *= G[i / v], i += v;
  while (i < n) res *= ++i;
  return res;
}

#line 1 "math/combinatorics/enumeration.hpp"
/**
 * @brief Enumeration(組み合わせ)
 */
template <typename T>
struct Enumeration {
 private:
  static vector<T> _fact, _finv, _inv;

  inline static void expand(size_t sz) {
    if (_fact.size() < sz + 1) {
      int pre_sz = max(1, (int)_fact.size());
      _fact.resize(sz + 1, T(1));
      _finv.resize(sz + 1, T(1));
      _inv.resize(sz + 1, T(1));
      for (int i = pre_sz; i <= (int)sz; i++) {
        _fact[i] = _fact[i - 1] * T(i);
      }
      _finv[sz] = T(1) / _fact[sz];
      for (int i = (int)sz - 1; i >= pre_sz; i--) {
        _finv[i] = _finv[i + 1] * T(i + 1);
      }
      for (int i = pre_sz; i <= (int)sz; i++) {
        _inv[i] = _finv[i] * _fact[i - 1];
      }
    }
  }

 public:
  explicit Enumeration(size_t sz = 0) { expand(sz); }

  static inline T fact(int k) {
    expand(k);
    return _fact[k];
  }

  static inline T finv(int k) {
    expand(k);
    return _finv[k];
  }

  static inline T inv(int k) {
    expand(k);
    return _inv[k];
  }

  static T P(int n, int r) {
    if (r < 0 || n < r) return 0;
    return fact(n) * finv(n - r);
  }

  static T C(int p, int q) {
    if (q < 0 || p < q) return 0;
    return fact(p) * finv(q) * finv(p - q);
  }

  static T H(int n, int r) {
    if (n < 0 || r < 0) return 0;
    return r == 0 ? 1 : C(n + r - 1, r);
  }
};

template <typename T>
vector<T> Enumeration<T>::_fact = vector<T>();
template <typename T>
vector<T> Enumeration<T>::_finv = vector<T>();
template <typename T>
vector<T> Enumeration<T>::_inv = vector<T>();
#line 2 "math/combinatorics/sample-point-shift.hpp"

/**
 * @brief Sample Point Shift(標本点シフト)
 */
template <typename Mint, typename F>
vector<Mint> sample_point_shift(const vector<Mint> &ys, const Mint &m,
                                const F &multiply) {
  Enumeration<Mint> comb;
  int d = (int)ys.size() - 1;
  vector<Mint> f(d + 1), g(d * 2 + 1);
  for (int i = 0; i <= d; i++) {
    f[i] = ys[i] * comb.finv(i) * comb.finv(d - i);
    if ((d - i) & 1) f[i] = -f[i];
  }
  for (int i = 0; i <= 2 * d; i++) {
    g[i] = Mint(1) / (m - d + i);
  }
  auto h = multiply(f, g);
  Mint coef = 1;
  for (int i = 0; i <= d; i++) {
    coef *= (m - d + i);
  }
  for (int i = 0; i <= d; i++) {
    h[i + d] *= coef;
    coef *= (m + i + 1) * g[i];
  }
  return vector<Mint>{begin(h) + d, begin(h) + 2 * d + 1};
}
#line 2 "math/combinatorics/factorial.hpp"

/**
 * @brief Factorial(階乗)
 */
template <typename Mint, typename F>
Mint factorial(int64_t n, const F& multiply) {
  if (n <= 1) return 1;
  if (n >= Mint::mod()) return 0;
  int64_t v = 1;
  while (v * v < n) v *= 2;
  Mint iv = Mint(1) / v;
  vector<Mint> G{1, v + 1};
  for (int64_t d = 1; d != v; d <<= 1) {
    vector<Mint> G1 = sample_point_shift(G, Mint(d) * iv, multiply);
    vector<Mint> G2 = sample_point_shift(G, Mint(d * v + v) * iv, multiply);
    vector<Mint> G3 = sample_point_shift(G, Mint(d * v + d + v) * iv, multiply);
    for (int i = 0; i <= d; i++) G[i] *= G1[i], G2[i] *= G3[i];
    copy(begin(G2), end(G2) - 1, back_inserter(G));
  }
  Mint res = 1;
  int64_t i = 0;
  while (i + v <= n) res *= G[i / v], i += v;
  while (i < n) res *= ++i;
  return res;
}

Back to top page