Skip to content

montmort.hpp

SECTIONMath INCLUDEnoya/montmort.hpp

生成错排数 \(D_0,\ldots,D_n\)；用于没有元素留在原位置的排列计数。

\[ \displaystyle D_n=(n-1)(D_{n-1}+D_{n-2}),\quad D_0=1,\ D_1=0 \]

Complexity: Time: O(n). Space: O(n) for all values, or O(1) when only the current recurrence state is retained.

AC 记录：montmort_number_mod。

跳到代码 · GitHub ↗

Implementation

当前头文件，省略 include guard；依赖见 #include。

/// @complexity Time: O(n).  Space: O(n) for all values, or O(1) when only the
/// current recurrence state is retained.

#include <cassert>
#include <cstdint>
#include <vector>

namespace noya {

/// @brief Return derangement counts D_0 through D_n modulo modulus.
/// Separating the position occupied by the image of the first element gives
/// D_n = (n-1)(D_{n-1}+D_{n-2}), with D_0=1 and D_1=0.
inline std::vector<std::uint64_t> montmort_numbers(int n, std::uint64_t mod) {
  assert(n >= 0 && mod >= 1);
  std::vector<std::uint64_t> res(n + 1);
  res[0] = 1 % mod;
  for (int sz = 2; sz <= n; sz++) {
    auto sum =
        (static_cast<unsigned __int128>(res[sz - 1]) + res[sz - 2]) % mod;
    res[sz] = std::uint64_t(static_cast<unsigned __int128>(sz - 1) * sum % mod);
  }
  return res;
}

} // namespace noya

#ifndef NOYA_MONTMORT_HPP
#define NOYA_MONTMORT_HPP 1

/// @complexity Time: O(n).  Space: O(n) for all values, or O(1) when only the
/// current recurrence state is retained.

#include <cassert>
#include <cstdint>
#include <vector>

namespace noya {

/// @brief Return derangement counts D_0 through D_n modulo modulus.
/// Separating the position occupied by the image of the first element gives
/// D_n = (n-1)(D_{n-1}+D_{n-2}), with D_0=1 and D_1=0.
inline std::vector<std::uint64_t> montmort_numbers(int n, std::uint64_t mod) {
  assert(n >= 0 && mod >= 1);
  std::vector<std::uint64_t> res(n + 1);
  res[0] = 1 % mod;
  for (int sz = 2; sz <= n; sz++) {
    auto sum =
        (static_cast<unsigned __int128>(res[sz - 1]) + res[sz - 2]) % mod;
    res[sz] = std::uint64_t(static_cast<unsigned __int128>(sz - 1) * sum % mod);
  }
  return res;
}

} // namespace noya

#endif // NOYA_MONTMORT_HPP

#include <cassert>
#include <cstdint>
#include <vector>

/// @complexity Time: O(n).  Space: O(n) for all values, or O(1) when only the
/// current recurrence state is retained.

namespace noya {

/// @brief Return derangement counts D_0 through D_n modulo modulus.
/// Separating the position occupied by the image of the first element gives
/// D_n = (n-1)(D_{n-1}+D_{n-2}), with D_0=1 and D_1=0.
inline std::vector<std::uint64_t> montmort_numbers(int n, std::uint64_t mod) {
  assert(n >= 0 && mod >= 1);
  std::vector<std::uint64_t> res(n + 1);
  res[0] = 1 % mod;
  for (int sz = 2; sz <= n; sz++) {
    auto sum =
        (static_cast<unsigned __int128>(res[sz - 1]) + res[sz - 2]) % mod;
    res[sz] = std::uint64_t(static_cast<unsigned __int128>(sz - 1) * sum % mod);
  }
  return res;
}

} // namespace noya