haar_lib/math/combinatorics/
bell_number.rs

1//! ベル数$B_0, \dots, B_n$を列挙する。
2use crate::math::prime_mod::PrimeMod;
3use crate::{
4    math::{factorial::FactorialTable, fps::exp::*, polynomial::*},
5    num::const_modint::*,
6};
7
8/// ベル数$B_0, \dots, B_n$を列挙する。
9pub fn bell_number<P: PrimeMod>(n: usize) -> Vec<ConstModInt<P>> {
10    let ft = FactorialTable::new(n, ConstModIntBuilder::new());
11    let mut f = vec![ConstModInt::new(0); n + 1];
12
13    for (i, fi) in f.iter_mut().enumerate().take(n + 1).skip(1) {
14        *fi = ft.inv_facto(i);
15    }
16
17    let mut ret: Vec<_> = Polynomial::from(f).fps_exp().unwrap().into();
18
19    for (i, reti) in ret.iter_mut().enumerate().take(n + 1) {
20        *reti *= ft.facto(i);
21    }
22
23    ret
24}

haar_lib/math/combinatorics/bell_number.rs

haar_lib/math/combinatorics/
bell_number.rs