haar_lib/math/combinatorics/
stirling_first_fixed_k.rs

1//! 符号付き第一種スターリング数$s(0, k), \dots, s(n, k)$を列挙する。
2use crate::math::factorial::FactorialTable;
3use crate::math::fps::pow::FpsPow;
4use crate::math::mod_ops::enum_inv::enumerate_mod_inv;
5use crate::math::polynomial::Polynomial;
6use crate::math::prime_mod::PrimeMod;
7use crate::num::const_modint::*;
8
9/// 符号付き第一種スターリング数$s(0, k), \dots, s(n, k)$を列挙する。
10pub fn stirling_first_fixed_k<P: PrimeMod>(n: usize, k: usize) -> Vec<ConstModInt<P>> {
11    assert!(k <= n);
12
13    let ft = FactorialTable::new(n, ConstModIntBuilder::new());
14
15    let mut ret: Vec<ConstModInt<P>> = enumerate_mod_inv(n, P::PRIME_NUM as u64)
16        .into_iter()
17        .map(Into::into)
18        .collect();
19
20    for i in (2..=n).step_by(2) {
21        ret[i] = -ret[i];
22    }
23
24    ret = Polynomial::from(ret).fps_pow(k as u64).unwrap().into();
25
26    for (i, reti) in ret.iter_mut().enumerate().take(n + 1).skip(k) {
27        *reti *= ft.inv_facto(k) * ft.facto(i);
28    }
29
30    ret
31}

haar_lib/math/combinatorics/stirling_first_fixed_k.rs

haar_lib/math/combinatorics/
stirling_first_fixed_k.rs