src/math/modular-arithmetic/small-mod-combination.hpp

• View this file on GitHub
• Last update: 2023-06-20 07:52:14+09:00
• Include: #include "src/math/modular-arithmetic/small-mod-combination.hpp"

Depends on

• src/cpp-template/header/size-alias.hpp
• src/math/modular-arithmetic/modular-combinatorics.hpp

Verified with

• test/atcoder/arc117_c.test.cpp

Code

#pragma once

#include "src/math/modular-arithmetic/modular-combinatorics.hpp"

namespace luz {

  template < typename modint >
  class SmallModCombination {
    static constexpr auto 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/math/modular-arithmetic/modular-combinatorics.hpp"

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

#include <cstddef>

namespace luz {

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

}
#line 4 "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 = bound; i < n; i++) {
        fact[i] = fact[i - 1] * i;
      }

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

      for (usize i = bound; i < n; i++) {
        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 4 "src/math/modular-arithmetic/small-mod-combination.hpp"

namespace luz {

  template < typename modint >
  class SmallModCombination {
    static constexpr auto 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