haar_lib/math/combinatorics/
stirling_first_table.rs

1//! 符号付き第一種スターリング数$s(0,0), \dots, s(n,n)$を列挙する。
2use crate::num::zz::*;
3
4/// 符号付き第一種スターリング数$s(0,0), \dots, s(n,n)$を列挙する。
5///
6/// **Time complexity** $O(n^2)$
7pub fn stirling_first_table<R: ZZ>(n: usize, modulo: R) -> Vec<Vec<R::Element>>
8where
9    R::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}