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>(n: usize) -> Vec<ConstModInt<P>> {
13    let ft = FactorialTable::new(n + 1, ConstModIntBuilder);
14    let ntt = NTT::<P, PR>::new();
15    let fps = PolynomialOperator::new(&ntt);
16    let mut x = vec![ConstModInt::new(0); n + 1];
17
18    for i in 0..=n {
19        x[i] = ft.inv_facto(i + 1);
20    }
21
22    x = fps.fps_inv(x.into()).unwrap().into();
23    for i in 0..=n {
24        x[i] *= ft.facto(i);
25    }
26
27    x
28}
29
30#[cfg(test)]
31mod tests {
32    use super::*;
33
34    use crate::math::factorial::bernoulli::BernoulliNumber;
35
36    #[test]
37    fn test() {
38        let n = 100;
39
40        let ff = ConstModIntBuilder::<998244353>;
41        let ft = FactorialTable::new(n + 1, ff);
42
43        assert_eq!(ft.bernoulli_number(n), bernoulli_number::<998244353, 3>(n));
44    }
45}
haar_lib/math/bernoulli_number.rs

haar_lib/math/
bernoulli_number.rs
