Montmort number
(Mylib/Combinatorics/montmort_number.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Link: View error logs on GitHub Actions

Operations

• montmort_number(int n)
  • 長さ$0$~$n$の完全順列の個数を列挙する。
  • Time complexity $O(n)$

Requirements

Notes

Problems

• ARC009 C - 高橋君、24歳
• Montmort Number

References

• https://ja.wikipedia.org/wiki/%E5%AE%8C%E5%85%A8%E9%A0%86%E5%88%97
• https://oeis.org/A000166

Verified with

• test/yosupo-judge/montmort_number_mod/main.test.cpp

Code

#pragma once
#include <vector>

namespace haar_lib {
  template <typename T>
  std::vector<T> montmort_number(int n) {
    std::vector<T> ret(n + 1);

    ret[0] = 1;
    ret[1] = 0;
    ret[2] = 1;

    for (int i = 3; i <= n; ++i) {
      ret[i] = (ret[i - 1] + ret[i - 2]) * (i - 1);
    }

    return ret;
  }
}  // namespace haar_lib

#line 2 "Mylib/Combinatorics/montmort_number.cpp"
#include <vector>

namespace haar_lib {
  template <typename T>
  std::vector<T> montmort_number(int n) {
    std::vector<T> ret(n + 1);

    ret[0] = 1;
    ret[1] = 0;
    ret[2] = 1;

    for (int i = 3; i <= n; ++i) {
      ret[i] = (ret[i - 1] + ret[i - 2]) * (i - 1);
    }

    return ret;
  }
}  // namespace haar_lib

Back to top page