haar_lib/math/
stirling_second_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_second_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, ret_i) in ret.iter_mut().enumerate().skip(1) {
16        ret_i[1] = modulo.from_u64(1);
17        ret_i[i] = modulo.from_u64(1);
18    }
19
20    for i in 3..=n {
21        for j in 2..i {
22            ret[i][j] = ret[i - 1][j - 1] + modulo.from_u64(j as u64) * ret[i - 1][j];
23        }
24    }
25
26    ret
27}