haar_lib/math/factorial/
stirling_second.rs

1//! 第二種スターリング数
2use crate::{math::factorial::FactorialTable, num::ff::*};
3
4/// 第二種スターリング数
5pub trait StirlingSecond {
6    /// 計算結果の型
7    type Output;
8    /// 第二種スターリング数$S(n,k)$を計算する。
9    fn stirling_second(&self, n: usize, k: usize) -> Self::Output;
10}
11
12impl<Modulo: FF> StirlingSecond for FactorialTable<Modulo>
13where
14    Modulo::Element: FFElem + Copy,
15{
16    type Output = Modulo::Element;
17
18    fn stirling_second(&self, n: usize, k: usize) -> Self::Output {
19        match (n, k) {
20            (0, 0) => self.modulo.from_u64(1),
21            (0, _) => self.modulo.from_u64(0),
22            _ => {
23                let mut ret = self.modulo.from_u64(0);
24
25                for i in 1..=k {
26                    if (k - i) % 2 == 0 {
27                        ret += self.comb(k, i) * self.modulo.from_u64(i as u64).pow(n as u64);
28                    } else {
29                        ret -= self.comb(k, i) * self.modulo.from_u64(i as u64).pow(n as u64);
30                    }
31                }
32                ret * self.inv_facto(k)
33            }
34        }
35    }
36}
haar_lib/math/factorial/stirling_second.rs

haar_lib/math/factorial/
stirling_second.rs
