haar_lib/math/
montmort.rs

1//! 完全順列の個数を列挙する。
2//!
3//! # References
4//! - <https://ja.wikipedia.org/wiki/%E5%AE%8C%E5%85%A8%E9%A0%86%E5%88%97>
5//! - <https://oeis.org/A000166>
6
7/// 長さ`0`から`n`までの完全順列の個数を列挙する。
8///
9/// **Time complexity** $O(n)$
10pub fn montmort(n: usize, m: u64) -> Vec<u64> {
11    let mut ret = vec![0; n + 1];
12
13    if n >= 2 {
14        ret[2] = 1;
15
16        for i in 3..=n {
17            ret[i] = (i - 1) as u64 * (ret[i - 1] + ret[i - 2]) % m;
18        }
19    }
20
21    ret
22}
23
24#[cfg(test)]
25mod tests {
26    use super::*;
27
28    #[test]
29    fn test() {
30        assert_eq!(montmort(10, 100)[1..], [0, 1, 2, 9, 44, 65, 54, 33, 96, 61]);
31        assert_eq!(
32            montmort(20, 998244353)[1..],
33            [
34                0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, 176214841, 294304226,
35                127281753, 910981941, 600290115, 222488424, 11814221, 224470198, 496426549
36            ]
37        );
38    }
39}
haar_lib/math/montmort.rs

haar_lib/math/
montmort.rs
