haar_lib/math/factorial/
catalan.rs

1//! カタラン数
2use crate::math::factorial::FactorialTable;
3use crate::num::ff::*;
4
5/// カタラン数
6pub trait CatalanNumber {
7    /// 計算結果の型
8    type Output;
9    /// カタラン数$C_n$を計算する。
10    fn catalan_number(&self, n: usize) -> Self::Output;
11}
12
13impl<Modulo: FF> CatalanNumber for FactorialTable<Modulo>
14where
15    Modulo::Element: FFElem + Copy,
16{
17    type Output = Modulo::Element;
18    fn catalan_number(&self, n: usize) -> Self::Output {
19        match n {
20            0 => self.modulo.from_u64(1),
21            _ => self.comb(2 * n, n) - self.comb(2 * n, n - 1),
22        }
23    }
24}
25
26#[cfg(test)]
27mod tests {
28    use super::*;
29    use crate::num::const_modint::*;
30
31    #[test]
32    fn test() {
33        let modulo = ConstModIntBuilder::<1000000007>;
34        let ft = FactorialTable::new(100, modulo);
35
36        let catalans = (0..=30).map(|i| ft.catalan_number(i)).collect::<Vec<_>>();
37
38        // https://oeis.org/A000108/list
39        let ans: Vec<u64> = vec![
40            1,
41            1,
42            2,
43            5,
44            14,
45            42,
46            132,
47            429,
48            1430,
49            4862,
50            16796,
51            58786,
52            208012,
53            742900,
54            2674440,
55            9694845,
56            35357670,
57            129644790,
58            477638700,
59            1767263190,
60            6564120420,
61            24466267020,
62            91482563640,
63            343059613650,
64            1289904147324,
65            4861946401452,
66            18367353072152,
67            69533550916004,
68            263747951750360,
69            1002242216651368,
70            3814986502092304,
71        ];
72        let ans = ans
73            .into_iter()
74            .map(|x| modulo.from_u64(x))
75            .collect::<Vec<_>>();
76
77        assert_eq!(catalans, ans);
78    }
79}
haar_lib/math/factorial/catalan.rs

haar_lib/math/factorial/
catalan.rs
