haar_lib/math/combinatorics/
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::polynomial::*;
8use crate::math::prime_mod::PrimeMod;
9use crate::num::const_modint::*;
10
11/// ベルヌーイ数$B_0, \dots, B_n$を列挙する。
12pub fn bernoulli_number<P: PrimeMod>(n: usize) -> Vec<ConstModInt<P>> {
13    let ft = FactorialTable::new(n + 1, ConstModIntBuilder::new());
14    let mut x = vec![ConstModInt::new(0); n + 1];
15
16    for (i, xi) in x.iter_mut().enumerate().take(n + 1) {
17        *xi = ft.inv_facto(i + 1);
18    }
19
20    x = Polynomial::from(x).fps_inv().unwrap().into();
21    for (i, xi) in x.iter_mut().enumerate().take(n + 1) {
22        *xi *= ft.facto(i);
23    }
24
25    x
26}
27
28#[cfg(test)]
29mod tests {
30    use super::*;
31
32    use crate::math::{factorial::bernoulli::BernoulliNumber, prime_mod::Prime};
33
34    type P = Prime<998244353>;
35
36    #[test]
37    fn test() {
38        let n = 100;
39
40        let ff = ConstModIntBuilder::<P>::new();
41        let ft = FactorialTable::new(n + 1, ff);
42
43        assert_eq!(ft.bernoulli_number(n), bernoulli_number::<P>(n));
44    }
45}

haar_lib/math/combinatorics/bernoulli_number.rs

haar_lib/math/combinatorics/
bernoulli_number.rs