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

• View this file on GitHub
• View document part on GitHub
• Last update: 2026-08-10 06:54:42+00:00
• Include: #include "math/combinatorics/montmort.hpp"

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

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

montmort

vector<T> montmort(int N)

n 番目のモンモール数を返す。

計算量

• $O(n)$

Verified with

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

Code

#pragma once

#include <vector>

/**
 * @brief Montmort-Number(モンモール数)
 *
 */
template <typename T>
std::vector<T> montmort(int N) {
  std::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 2 "math/combinatorics/montmort.hpp"

#include <vector>

/**
 * @brief Montmort-Number(モンモール数)
 *
 */
template <typename T>
std::vector<T> montmort(int N) {
  std::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