Montmort-Number(モンモール数) (math/combinatorics/montmort.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-05-01 23:44:47+09:00
• Include: #include "math/combinatorics/montmort.hpp"

概要

完全順列の総数をモンモール数とよぶ.

長さ $n$ の完全順列とは, 長さ $n$ の順列であって $i(1 \leq i \leq N)$ 番目の要素が $i$ でない順列を指す.

• montmort(n): n 番目のモンモール数を返す.

計算量

• $O(n)$

Verified with

• test/verify/yosupo-montmort-number-mod.test.cpp

Code

/**
 * @brief Montmort-Number(モンモール数)
 *
 */
template <typename T>
vector<T> montmort(int N) {
  vector<T> dp(N + 1);
  for (int k = 2; k <= N; k++) {
    dp[k] = dp[k - 1] * k;
    if (k & 1)
      dp[k] -= 1;
    else
      dp[k] += 1;
  }
  return dp;
}

#line 1 "math/combinatorics/montmort.hpp"
/**
 * @brief Montmort-Number(モンモール数)
 *
 */
template <typename T>
vector<T> montmort(int N) {
  vector<T> dp(N + 1);
  for (int k = 2; k <= N; k++) {
    dp[k] = dp[k - 1] * k;
    if (k & 1)
      dp[k] -= 1;
    else
      dp[k] += 1;
  }
  return dp;
}

Back to top page