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>(
9    n: usize,
10    ft: &FactorialTable<ConstModIntBuilder<P>>,
11    ntt: &NTT<P, PR>,
12) -> Vec<ConstModInt<P>> {
13    let fps = PolynomialOperator::new(ntt);
14    let mut f = vec![ConstModInt::new(0); n + 1];
15
16    for i in 1..=n {
17        f[i] = ft.inv_facto(i);
18    }
19
20    let mut ret: Vec<_> = fps.fps_exp(f.into()).into();
21
22    for i in 0..=n {
23        ret[i] *= ft.facto(i);
24    }
25
26    ret
27}