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。
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 <cstddef>
#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(std::size_t(n) + 1);
res[0] = 1 % mod;
for (std::size_t sz = 2; sz < res.size(); sz++) {
auto sum =
static_cast<unsigned __int128>(res[sz - 1]) + res[sz - 2];
res[sz] = std::uint64_t(static_cast<unsigned __int128>(sz - 1) * sum % mod);
}
return res;
}
} // namespace noya
// NOYA_MONTMORT_HPP
#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 <cstddef>
#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(std::size_t(n) + 1);
res[0] = 1 % mod;
for (std::size_t sz = 2; sz < res.size(); sz++) {
auto sum =
static_cast<unsigned __int128>(res[sz - 1]) + res[sz - 2];
res[sz] = std::uint64_t(static_cast<unsigned __int128>(sz - 1) * sum % mod);
}
return res;
}
} // namespace noya
#endif // NOYA_MONTMORT_HPP
/// @complexity Time: O(n). Space: O(n) for all values, or O(1) when only the
/// current recurrence state is retained.
#include <cassert>
#include <cstddef>
#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(std::size_t(n) + 1);
res[0] = 1 % mod;
for (std::size_t sz = 2; sz < res.size(); sz++) {
auto sum =
static_cast<unsigned __int128>(res[sz - 1]) + res[sz - 2];
res[sz] = std::uint64_t(static_cast<unsigned __int128>(sz - 1) * sum % mod);
}
return res;
}
} // namespace noya
// NOYA_MONTMORT_HPP