haar_lib/math/
bernoulli_number.rs

1//! ベルヌーイ数$B_0, \dots, B_n$を列挙する。
2//!
3//! # Problems
4//! - <https://judge.yosupo.jp/problem/bernoulli_number>
5use crate::math::factorial::FactorialTable;
6use crate::math::fps::inv::*;
7use crate::math::ntt::*;
8use crate::math::polynomial::*;
9use crate::num::const_modint::*;
10
11/// ベルヌーイ数$B_0, \dots, B_n$を列挙する。
12pub fn bernoulli_number<const P: u32, const PR: u32>(
13    n: usize,
14    ft: &FactorialTable<ConstModIntBuilder<P>>,
15    ntt: &NTT<P, PR>,
16) -> Vec<ConstModInt<P>> {
17    let ff = ConstModIntBuilder;
18    let fps = PolynomialOperator::new(ntt);
19    let mut x: Polynomial<P> = vec![ff.from_u64(0); n + 1].into();
20
21    for i in 0..=n {
22        x[i] = ft.inv_facto(i + 1);
23    }
24
25    x = fps.fps_inv(x);
26    for i in 0..=n {
27        x[i] *= ft.facto(i);
28    }
29
30    x.into()
31}
32
33#[cfg(test)]
34mod tests {
35    use super::*;
36
37    use crate::math::factorial::bernoulli::BernoulliNumber;
38
39    #[test]
40    fn test() {
41        let n = 100;
42
43        let ff = ConstModIntBuilder::<998244353>;
44        let ntt = NTT::<998244353, 3>::new();
45        let ft = FactorialTable::new(n + 1, ff);
46
47        assert_eq!(ft.bernoulli_number(n), bernoulli_number(n, &ft, &ntt));
48    }
49}
haar_lib/math/bernoulli_number.rs

haar_lib/math/
bernoulli_number.rs
