haar_lib/math/combinatorics/
stirling_first.rs

1//! 符号付き第一種スターリング数$s(n, 0), \dots, s(n, n)$を列挙する。
2//!
3//! $s(n,k)$ は $$x(x-1)\dots (x-(n-1)) = \sum_{k=0}^n s(n,k) x^k$$を満たす。
4use crate::math::convolution::ntt::NTT;
5use crate::math::polynomial::{polynomial_taylor_shift::*, Polynomial};
6use crate::math::prime_mod::PrimeMod;
7use crate::num::const_modint::*;
8
9/// 符号付き第一種スターリング数$s(n, 0), \dots, s(n, n)$を列挙する。
10///
11/// **Time complexity** $O(n \log n)$
12pub fn stirling_first<P: PrimeMod>(n: usize) -> Vec<ConstModInt<P>> {
13    let ff = ConstModIntBuilder::new();
14
15    let mut ret = Polynomial::<P>::from(vec![1]);
16    let ntt = NTT::<P>::new();
17
18    let mut t: usize = 0;
19    let mut check = false;
20
21    for i in (0..usize::BITS).rev() {
22        if check {
23            let s = ret.clone().taylor_shift(-ff.from_u64(t as u64));
24            ret = ntt.convolve(ret.into(), s.into()).into();
25            ret.as_mut().truncate(t * 2 + 1);
26            t *= 2;
27        }
28
29        if (n & (1 << i)) != 0 {
30            let a = vec![-ff.from_u64(t as u64), ff.from_u64(1)];
31            ret = ntt.convolve(ret.into(), a).into();
32            t += 1;
33
34            check = true;
35        }
36    }
37
38    ret.as_mut().truncate(n + 1);
39    ret.into()
40}
41
42#[cfg(test)]
43mod tests {
44    use crate::math::prime_mod::Prime;
45
46    use super::*;
47
48    type P = Prime<998244353>;
49
50    #[test]
51    fn test() {
52        let ff = ConstModIntBuilder::<P>::new();
53
54        let n = 100;
55        let mut ans = Polynomial::from(vec![ff.from_u64(1)]);
56
57        for i in 1..=n {
58            let res = stirling_first::<P>(i);
59
60            ans *= Polynomial::from(vec![-ff.from_u64(i as u64 - 1), 1.into()]);
61
62            assert_eq!(res, ans.as_ref());
63        }
64    }
65}
haar_lib/math/combinatorics/stirling_first.rs

haar_lib/math/combinatorics/
stirling_first.rs
