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

• View this file on GitHub
• Last update: 2022-09-11 00:53:50+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(モンモール数)
 * @docs docs/montmort.md
 */
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(モンモール数)
 * @docs docs/montmort.md
 */
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