haar_lib/math/combinatorics/
stirling_second_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::polynomial::Polynomial;
5use crate::math::prime_mod::PrimeMod;
6use crate::num::const_modint::*;
7
8/// 第二種スターリング数$S(0, k), \dots, S(n, k)$を列挙する。
9pub fn stirling_second_fixed_k<P: PrimeMod>(n: usize, k: usize) -> Vec<ConstModInt<P>> {
10    assert!(k <= n);
11
12    let ft = FactorialTable::new(n, ConstModIntBuilder::new());
13
14    let mut ret = vec![ConstModInt::new(0); n + 1];
15
16    for (i, reti) in ret.iter_mut().enumerate().take(n + 1).skip(1) {
17        *reti = ft.inv_facto(i);
18    }
19
20    ret = Polynomial::from(ret).fps_pow(k as u64).unwrap().into();
21
22    for (i, reti) in ret.iter_mut().enumerate().take(n + 1).skip(k) {
23        *reti *= ft.inv_facto(k) * ft.facto(i);
24    }
25
26    ret
27}