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::{
27        math::{ntt::NTT998244353, stirling_first::stirling_first},
28        num::const_modint::ConstModIntBuilder,
29    };
30
31    use super::*;
32
33    #[test]
34    fn test() {
35        let modulo = ConstModIntBuilder::<998244353>;
36        let ntt = NTT998244353::new();
37
38        let n = 100;
39        let table = stirling_first_table(n, modulo);
40
41        for i in 0..=n {
42            let ans = stirling_first(i, &ntt);
43
44            assert_eq!(&table[i][..=i], ans);
45        }
46    }
47}
haar_lib/math/stirling_first_table.rs

haar_lib/math/
stirling_first_table.rs
