haar_lib/math/
stirling_first_table.rs

1//! 符号付き第一種スターリング数$s(0,0), \dots, s(n,n)$を列挙する。
2use crate::num::ff::*;
3
4/// 符号付き第一種スターリング数$s(0,0), \dots, s(n,n)$を列挙する。
5///
6/// **Time complexity** $O(n^2)$
7pub fn stirling_first_table<Modulo: FF>(n: usize, modulo: Modulo) -> Vec<Vec<Modulo::Element>>
8where
9    Modulo::Element: Copy,
10{
11    let mut ret = vec![vec![modulo.from_u64(0); n + 1]; n + 1];
12
13    ret[0][0] = modulo.from_u64(1);
14
15    for i in 1..=n {
16        for j in 1..=i {
17            ret[i][j] = -modulo.from_u64(i as u64 - 1) * ret[i - 1][j] + ret[i - 1][j - 1]
18        }
19    }
20
21    ret
22}
23
24#[cfg(test)]
25mod tests {
26    use crate::{math::stirling_first::stirling_first, num::const_modint::ConstModIntBuilder};
27
28    use super::*;
29
30    #[test]
31    fn test() {
32        let modulo = ConstModIntBuilder::<998244353>;
33
34        let n = 100;
35        let table = stirling_first_table(n, modulo);
36
37        for i in 0..=n {
38            let ans = stirling_first::<998244353, 3>(i);
39
40            assert_eq!(&table[i][..=i], ans);
41        }
42    }
43}
haar_lib/math/stirling_first_table.rs

haar_lib/math/
stirling_first_table.rs
