mod 組合せ (mod combinatorics)
(src/math/modular-arithmetic/modular-combinatorics.hpp)

• View this file on GitHub
• Last update: 2023-07-30 00:54:52+09:00
• Include: #include "src/math/modular-arithmetic/modular-combinatorics.hpp"

コンストラクタ

Combinatorics<mint>(usize n = 0)

制約

• $0 \leq n$

計算量

• $n + f(p)$
  • $f(p)$ を mint の除算にかかる計算量とする。
  • mint が扱う $mod$ を $P$ として $O(\log P)$ であることが多い。

factorial

mint factorial(usize n)

$n!$ を計算する。

制約

• $0 \leq n$

計算量

• $O(1)$

factorial_inverse

mint factorial_inverse(usize n)

$(n!)^{-1}$ を計算する。

制約

• $0 \leq n$

計算量

• $O(1)$

inverse

mint inverse(usize n)

$n^{-1}$ を計算する。

制約

• $0 \leq n$

計算量

• $O(1)$

permutation

mint permutation(isize n, isize r)
mint P(isize n, isize r)

$_n\mathrm{P}_r$ を計算する。

$r < 0$ または $n < r$ のときは $0$ が返る。

計算量

• $O(1)$

combination

mint combination(isize n, isize r)
mint C(isize n, isize r)

$_n\mathrm{C}_r$ を計算する。

$r < 0$ または $n < r$ のときは $0$ が返る。

計算量

• $O(1)$

combination_with_repetitions

mint combination_with_repetitions(isize n, isize r)
mint H(isize n, isize r)

$_n\mathrm{H}_r$ を計算する。

$r < 0$ または $n < 0$ のときは $0$ が返る。

ボール $n$ 個、箱$k$ 個の場合は $_k\mathrm{H}_n$ であることに注意。

計算量

• $O(1)$

Depends on

• rep 構造体 (src/cpp-template/header/rep.hpp)
• size alias (src/cpp-template/header/size-alias.hpp)

Required by

• mod が小さい場合の combination (Lucas's theorem) (src/math/modular-arithmetic/small-mod-combination.hpp)

Verified with

• test/atcoder/abc132_d.test.cpp
• test/atcoder/arc117_c.test.cpp

Code

#pragma once

#include "src/cpp-template/header/rep.hpp"
#include "src/cpp-template/header/size-alias.hpp"

#include <vector>

namespace luz {

  template < typename mint >
  class Combinatorics {
    static usize bound;
    static std::vector< mint > fact, finv, inv;

    static void expand(usize n) {
      n += 1;
      if (fact.size() >= n) return;

      if (bound == 0) bound = 1;

      fact.resize(n, mint(1));
      finv.resize(n, mint(1));
      inv.resize(n, mint(1));

      for (usize i: rep(bound, n)) {
        fact[i] = fact[i - 1] * i;
      }

      finv.back() = mint(1) / fact.back();
      for (usize i: rrep(bound, n)) {
        finv[i - 1] = finv[i] * i;
      }

      for (usize i: rep(bound, n)) {
        inv[i] = finv[i] * fact[i - 1];
      }

      bound = n;
    }

   public:
    explicit Combinatorics(usize n = 0) {
      expand(n);
    }

    static mint factorial(usize n) {
      expand(n);
      return fact[n];
    }

    static mint factorial_inverse(usize n) {
      expand(n);
      return finv[n];
    }

    static mint inverse(usize n) {
      expand(n);
      return inv[n];
    }

    static mint permutation(isize n, isize r) {
      if (r < 0 or n < r) return 0;

      expand(n);
      return fact[n] * finv[n - r];
    }

    static mint combination(isize n, isize r) {
      if (r < 0 or n < r) return 0;

      expand(n);
      return fact[n] * finv[r] * finv[n - r];
    }

    static mint combination_with_repetitions(isize n, isize r) {
      if (n < 0 or r < 0) return 0;
      return (r ? combination(n + r - 1, r) : 1);
    }

    static mint P(isize n, isize r) {
      return permutation(n, r);
    }

    static mint C(isize n, isize r) {
      return combination(n, r);
    }

    static mint H(isize n, isize r) {
      return combination_with_repetitions(n, r);
    }
  };

  template < typename mint >
  usize Combinatorics< mint >::bound = 0;

  template < typename mint >
  std::vector< mint > Combinatorics< mint >::fact =
      std::vector< mint >();

  template < typename mint >
  std::vector< mint > Combinatorics< mint >::finv =
      std::vector< mint >();

  template < typename mint >
  std::vector< mint > Combinatorics< mint >::inv =
      std::vector< mint >();

} // namespace luz

#line 2 "src/math/modular-arithmetic/modular-combinatorics.hpp"

#line 2 "src/cpp-template/header/rep.hpp"

#line 2 "src/cpp-template/header/size-alias.hpp"

#include <cstddef>

namespace luz {

  using isize = std::ptrdiff_t;
  using usize = std::size_t;

} // namespace luz
#line 4 "src/cpp-template/header/rep.hpp"

#include <algorithm>

namespace luz {

  struct rep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        ++i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rep(const usize f, const usize l) noexcept
        : f(std::min(f, l)),
          l(l) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

  struct rrep {
    struct itr {
      usize i;
      constexpr itr(const usize i) noexcept: i(i) {}
      void operator++() noexcept {
        --i;
      }
      constexpr usize operator*() const noexcept {
        return i;
      }
      constexpr bool operator!=(const itr x) const noexcept {
        return i != x.i;
      }
    };
    const itr f, l;
    constexpr rrep(const usize f, const usize l) noexcept
        : f(l - 1),
          l(std::min(f, l) - 1) {}
    constexpr auto begin() const noexcept {
      return f;
    }
    constexpr auto end() const noexcept {
      return l;
    }
  };

} // namespace luz
#line 5 "src/math/modular-arithmetic/modular-combinatorics.hpp"

#include <vector>

namespace luz {

  template < typename mint >
  class Combinatorics {
    static usize bound;
    static std::vector< mint > fact, finv, inv;

    static void expand(usize n) {
      n += 1;
      if (fact.size() >= n) return;

      if (bound == 0) bound = 1;

      fact.resize(n, mint(1));
      finv.resize(n, mint(1));
      inv.resize(n, mint(1));

      for (usize i: rep(bound, n)) {
        fact[i] = fact[i - 1] * i;
      }

      finv.back() = mint(1) / fact.back();
      for (usize i: rrep(bound, n)) {
        finv[i - 1] = finv[i] * i;
      }

      for (usize i: rep(bound, n)) {
        inv[i] = finv[i] * fact[i - 1];
      }

      bound = n;
    }

   public:
    explicit Combinatorics(usize n = 0) {
      expand(n);
    }

    static mint factorial(usize n) {
      expand(n);
      return fact[n];
    }

    static mint factorial_inverse(usize n) {
      expand(n);
      return finv[n];
    }

    static mint inverse(usize n) {
      expand(n);
      return inv[n];
    }

    static mint permutation(isize n, isize r) {
      if (r < 0 or n < r) return 0;

      expand(n);
      return fact[n] * finv[n - r];
    }

    static mint combination(isize n, isize r) {
      if (r < 0 or n < r) return 0;

      expand(n);
      return fact[n] * finv[r] * finv[n - r];
    }

    static mint combination_with_repetitions(isize n, isize r) {
      if (n < 0 or r < 0) return 0;
      return (r ? combination(n + r - 1, r) : 1);
    }

    static mint P(isize n, isize r) {
      return permutation(n, r);
    }

    static mint C(isize n, isize r) {
      return combination(n, r);
    }

    static mint H(isize n, isize r) {
      return combination_with_repetitions(n, r);
    }
  };

  template < typename mint >
  usize Combinatorics< mint >::bound = 0;

  template < typename mint >
  std::vector< mint > Combinatorics< mint >::fact =
      std::vector< mint >();

  template < typename mint >
  std::vector< mint > Combinatorics< mint >::finv =
      std::vector< mint >();

  template < typename mint >
  std::vector< mint > Combinatorics< mint >::inv =
      std::vector< mint >();

} // namespace luz

Back to top page