comp-library

This documentation is automatically generated by online-judge-tools/verification-helper

View the Project on GitHub luzhiled1333/comp-library

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

コンストラクタ

SmallModCombination< modint >()

計算量

combination

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

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

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

計算量

Depends on

Verified with

Code

#pragma once

#include "src/cpp-template/header/int-alias.hpp"
#include "src/cpp-template/header/size-alias.hpp"
#include "src/math/modular-arithmetic/modular-combinatorics.hpp"

namespace luz {

  template < typename modint >
  class SmallModCombination {
    static constexpr u32 mod = modint::get_mod();
    Combinatorics< modint > mc;

   public:
    SmallModCombination(): mc(mod - 1) {}

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

      modint result(1);
      while (n) {
        result *= mc.combination(n % mod, r % mod);
        n /= mod;
        r /= mod;
      }

      return result;
    }

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

} // namespace luz
#line 2 "src/math/modular-arithmetic/small-mod-combination.hpp"

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

#include <cstdint>

namespace luz {

  using i32  = std::int32_t;
  using i64  = std::int64_t;
  using i128 = __int128_t;

  using u32  = std::uint32_t;
  using u64  = std::uint64_t;
  using u128 = __uint128_t;

} // namespace luz
#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 2 "src/math/modular-arithmetic/modular-combinatorics.hpp"

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

#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
#line 6 "src/math/modular-arithmetic/small-mod-combination.hpp"

namespace luz {

  template < typename modint >
  class SmallModCombination {
    static constexpr u32 mod = modint::get_mod();
    Combinatorics< modint > mc;

   public:
    SmallModCombination(): mc(mod - 1) {}

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

      modint result(1);
      while (n) {
        result *= mc.combination(n % mod, r % mod);
        n /= mod;
        r /= mod;
      }

      return result;
    }

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

} // namespace luz
Back to top page