haar_lib/math/
bell_number.rs

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

haar_lib/math/bell_number.rs

haar_lib/math/
bell_number.rs