二項係数他 (階乗前計算) ($\mathbb{F}_p$) (src/Math/FactorialPrecalculation.hpp)

View this file on GitHub
View document part on GitHub
Last update: 2024-10-14 13:39:24+09:00
Include: #include "src/Math/FactorialPrecalculation.hpp"

Depends on

modintを扱うテンプレート (src/Internal/modint_traits.hpp)

Required by

Verified with

Code

#pragma once
#include <cassert>
#include <vector>
#include "src/Internal/modint_traits.hpp"
template <class mod_t> class FactorialPrecalculation {
 static_assert(is_modint_v<mod_t>);
 static inline std::vector<mod_t> iv, fct, fiv;
public:
 static void reset() { iv.clear(), fct.clear(), fiv.clear(); }
 static inline mod_t inv(int n) {
  assert(0 < n);
  if (int k= iv.size(); k <= n) {
   if (iv.resize(n + 1); !k) iv[1]= 1, k= 2;
   for (unsigned long long mod= mod_t::mod(), q; k <= n; ++k) q= (mod + k - 1) / k, iv[k]= iv[k * q - mod] * q;
  }
  return iv[n];
 }
 static inline mod_t fact(int n) {
  assert(0 <= n);
  if (int k= fct.size(); k <= n) {
   if (fct.resize(n + 1); !k) fct[0]= 1, k= 1;
   for (; k <= n; ++k) fct[k]= fct[k - 1] * k;
  }
  return fct[n];
 }
 static inline mod_t finv(int n) {
  assert(0 <= n);
  if (int k= fiv.size(); k <= n) {
   if (fiv.resize(n + 1); !k) fiv[0]= 1, k= 1;
   for (; k <= n; ++k) fiv[k]= fiv[k - 1] * inv(k);
  }
  return fiv[n];
 }
 static inline mod_t nPr(int n, int r) { return r < 0 || n < r ? mod_t(0) : fact(n) * finv(n - r); }
 // [x^r] (1 + x)^n
 static inline mod_t nCr(int n, int r) { return r < 0 || n < r ? mod_t(0) : fact(n) * finv(n - r) * finv(r); }
 // [x^r] (1 - x)^{-n}
 static inline mod_t nHr(int n, int r) { return !r ? mod_t(1) : nCr(n + r - 1, r); }
};

#line 2 "src/Math/FactorialPrecalculation.hpp"
#include <cassert>
#include <vector>
#line 2 "src/Internal/modint_traits.hpp"
#include <type_traits>
namespace math_internal {
struct m_b {};
struct s_b: m_b {};
}
template <class mod_t> constexpr bool is_modint_v= std::is_base_of_v<math_internal::m_b, mod_t>;
template <class mod_t> constexpr bool is_staticmodint_v= std::is_base_of_v<math_internal::s_b, mod_t>;
#line 5 "src/Math/FactorialPrecalculation.hpp"
template <class mod_t> class FactorialPrecalculation {
 static_assert(is_modint_v<mod_t>);
 static inline std::vector<mod_t> iv, fct, fiv;
public:
 static void reset() { iv.clear(), fct.clear(), fiv.clear(); }
 static inline mod_t inv(int n) {
  assert(0 < n);
  if (int k= iv.size(); k <= n) {
   if (iv.resize(n + 1); !k) iv[1]= 1, k= 2;
   for (unsigned long long mod= mod_t::mod(), q; k <= n; ++k) q= (mod + k - 1) / k, iv[k]= iv[k * q - mod] * q;
  }
  return iv[n];
 }
 static inline mod_t fact(int n) {
  assert(0 <= n);
  if (int k= fct.size(); k <= n) {
   if (fct.resize(n + 1); !k) fct[0]= 1, k= 1;
   for (; k <= n; ++k) fct[k]= fct[k - 1] * k;
  }
  return fct[n];
 }
 static inline mod_t finv(int n) {
  assert(0 <= n);
  if (int k= fiv.size(); k <= n) {
   if (fiv.resize(n + 1); !k) fiv[0]= 1, k= 1;
   for (; k <= n; ++k) fiv[k]= fiv[k - 1] * inv(k);
  }
  return fiv[n];
 }
 static inline mod_t nPr(int n, int r) { return r < 0 || n < r ? mod_t(0) : fact(n) * finv(n - r); }
 // [x^r] (1 + x)^n
 static inline mod_t nCr(int n, int r) { return r < 0 || n < r ? mod_t(0) : fact(n) * finv(n - r) * finv(r); }
 // [x^r] (1 - x)^{-n}
 static inline mod_t nHr(int n, int r) { return !r ? mod_t(1) : nCr(n + r - 1, r); }
};

二項係数 他 (階乗前計算) ($\mathbb{F}_p$) (src/Math/FactorialPrecalculation.hpp)

Depends on

Required by

Verified with

Code

二項係数他 (階乗前計算) ($\mathbb{F}_p$) (src/Math/FactorialPrecalculation.hpp)