モンモール数 (完全順列)
(Combination/montmort_number.py)

• View this file on GitHub
• Last update: 2021-01-27 22:05:50+09:00

概要

整数 $1, 2, \dots , n$ を並び替えてできる順列において、$i$ 番目 ($1 \le i \le n$) が $i$ でない順列を完全順列 (撹拌順列) という。完全順列となる通り数 $a_n$ をモンモール数という。

モンモール数は以下の漸化式で考えることができる。

\[a_n=(n-1)(a_{n-1}+a_{n-2})\]

また、一般項を計算すると以下の式となる。

\[a_n=n!\sum_{k=2}^n\frac{(-1)^k}{k!}\]

漸化式の導出と包除原理による一般項の導出は 高校数学の美しい物語 が分かりやすい。具体的な数列は OEIS A000166 を参照。

使い方

montmort_number(n: int, MOD: int) -> List[int]
MOD 上での第 n 項までのモンモール数のリストを返す。計算量 $O(n)$

montmort_number2(n: int, MOD: int) -> List[int]
MOD 上での第 n 項までのモンモール数のリストを返す。計算量 $O(n)$

備考

漸化式の計算のイメージ

Verified with

• TestCase/LibraryChecker/montmort_number_mod.test.py

Code

def montmort_number(n, MOD):
    dp = [0] * (n + 1)
    if n >= 2:
        dp[2] = 1
    for i in range(3, n + 1):
        dp[i] = (i - 1) * (dp[i - 1] + dp[i - 2])
        dp[i] %= MOD
    return dp


def montmort_number2(n, MOD):
    dp = [0] * (n + 1)
    for i in range(1, n):
        dp[i + 1] = (i + 1) * dp[i] + (-1) ** ((i + 1) & 1)
        dp[i + 1] %= MOD
    return dp

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page