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
19#[cfg(test)]
20mod tests {
21    use super::{exp::*, inv::*, log::*, pow::*};
22
23    use crate::math::ntt::*;
24    use crate::math::polynomial::*;
25
26    #[test]
27    fn test_inv() {
28        let ntt = NTT998244353::new();
29        let po = PolynomialOperator::new(&ntt);
30
31        let a: Vec<u32> = vec![5, 4, 3, 2, 1];
32        let b = po.fps_inv(a.clone().into());
33
34        assert_eq!(
35            po.mul(a.into(), b).get_until(5),
36            Polynomial::constant(1_u32.into())
37        );
38    }
39
40    #[test]
41    fn test_log() {
42        let ntt = NTT998244353::new();
43        let po = PolynomialOperator::new(&ntt);
44
45        let a: Vec<u32> = vec![1, 1, 499122179, 166374064, 291154613];
46        let b = po.fps_log(a.clone().into());
47
48        assert_eq!(b, vec![0, 1, 2, 3, 4].into());
49    }
50
51    #[test]
52    fn test_exp() {
53        let ntt = NTT998244353::new();
54        let po = PolynomialOperator::new(&ntt);
55
56        let a: Vec<u32> = vec![0, 1, 2, 3, 4];
57        let b = po.fps_exp(a.clone().into());
58        let b = po.fps_log(b);
59
60        assert_eq!(b, a.into());
61    }
62
63    #[test]
64    fn test_pow() {
65        let ntt = NTT998244353::new();
66        let po = PolynomialOperator::new(&ntt);
67
68        let a: Vec<u32> = vec![0, 0, 9, 2];
69        let b = po.fps_pow(a.clone().into(), 3);
70        assert_eq!(b, vec![0, 0, 0, 0].into());
71
72        let a: Vec<u32> = vec![1, 1];
73        let b = po.fps_pow(a.clone().into(), 2);
74        assert_eq!(b, vec![1, 2].into());
75
76        let a: Vec<u32> = vec![0, 0];
77        let b = po.fps_pow(a.clone().into(), 0);
78        dbg!(b);
79    }
80}
haar_lib/math/fps/mod.rs

haar_lib/math/fps/
mod.rs
