haar_lib/math/fps/
mod.rs

1//! Formal Power Series
2//!
3//! # References
4//! - <https://maspypy.com/%E5%A4%9A%E9%A0%85%E5%BC%8F%E3%83%BB%E5%BD%A2%E5%BC%8F%E7%9A%84%E3%81%B9%E3%81%8D%E7%B4%9A%E6%95%B0%E6%95%B0%E3%81%88%E4%B8%8A%E3%81%92%E3%81%A8%E3%81%AE%E5%AF%BE%E5%BF%9C%E4%BB%98%E3%81%91>
5//! - <https://qiita.com/hotman78/items/f0e6d2265badd84d429a>
6//!
7//! # Problems
8//! - <https://judge.yosupo.jp/problem/inv_of_formal_power_series>
9//! - <https://judge.yosupo.jp/problem/log_of_formal_power_series>
10//! - <https://judge.yosupo.jp/problem/exp_of_formal_power_series>
11//! - <https://judge.yosupo.jp/problem/pow_of_formal_power_series>
12
13pub mod exp;
14pub mod inv;
15pub mod log;
16pub mod pow;
17pub mod sqrt;
18
19pub mod exp_sparse;
20pub mod inv_sparse;
21pub mod log_sparse;
22pub mod pow_sparse;
23pub mod sqrt_sparse;
24
25#[cfg(test)]
26mod tests {
27    use super::{exp::*, inv::*, log::*, pow::*};
28
29    use crate::math::polynomial::*;
30    use crate::math::prime_mod::Prime;
31
32    type P = Prime<998244353>;
33
34    #[test]
35    fn test_inv() {
36        let a = Polynomial::<P>::from(vec![5, 4, 3, 2, 1]);
37        let b = a.clone().fps_inv().unwrap();
38
39        assert_eq!((a * b).get_until(5), Polynomial::constant(1_u32.into()));
40    }
41
42    #[test]
43    fn test_log() {
44        let a = Polynomial::<P>::from(vec![1, 1, 499122179, 166374064, 291154613]);
45        let b = a.fps_log().unwrap();
46
47        assert_eq!(b, vec![0, 1, 2, 3, 4].into());
48    }
49
50    #[test]
51    fn test_exp() {
52        let a = Polynomial::<P>::from(vec![0, 1, 2, 3, 4]);
53        let b = a.clone().fps_exp().unwrap();
54        let b = b.fps_log().unwrap();
55
56        assert_eq!(b, a);
57    }
58
59    #[test]
60    fn test_pow() {
61        let a = Polynomial::<P>::from(vec![0, 0, 9, 2]);
62        let b = a.clone().fps_pow(3).unwrap();
63        assert_eq!(b, vec![0, 0, 0, 0].into());
64
65        let a = Polynomial::<P>::from(vec![1, 1]);
66        let b = a.clone().fps_pow(2).unwrap();
67        assert_eq!(b, vec![1, 2].into());
68
69        let a = Polynomial::<P>::from(vec![0, 0]);
70        let b = a.clone().fps_pow(0).unwrap();
71        dbg!(b);
72    }
73}
haar_lib/math/fps/mod.rs

haar_lib/math/fps/
mod.rs
