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

haar_lib/math/fps/
mod.rs
