haar_lib/math/fps/
log_sparse.rs

1//! 疎な形式的冪級数の対数
2use crate::math::fps::inv_sparse::*;
3use crate::math::polynomial::sparse::SparsePolynomial;
4use crate::math::polynomial::Polynomial;
5use crate::math::prime_mod::PrimeMod;
6use crate::num::const_modint::*;
7
8/// 疎な形式的冪級数の対数
9pub trait FpsLogSparse {
10    /// 戻り値の型
11    type Output;
12
13    /// $f(x) = \sum_0^{n-1} a_ix^i$について、$\log f(x)$の先頭$n$項を求める。
14    fn fps_log_sparse(self, n: usize) -> Result<Self::Output, &'static str>;
15}
16
17impl<P: PrimeMod> FpsLogSparse for SparsePolynomial<P> {
18    type Output = Polynomial<P>;
19
20    /// **Time complexity** $O(nk)$
21    fn fps_log_sparse(self, n: usize) -> Result<Self::Output, &'static str> {
22        let mut f = self.clone();
23        f.differential();
24
25        let g = self.fps_inv_sparse(n)?;
26
27        let mut h = vec![ConstModInt::new(0); n];
28        for (&i, &x) in f.iter() {
29            for (&y, h) in g.data.iter().zip(h.iter_mut().skip(i)) {
30                *h += x * y;
31            }
32        }
33
34        let mut invs = vec![ConstModInt::new(1); n + 1];
35        for i in 2..=n {
36            invs[i] = -invs[P::PRIME_NUM as usize % i] * ConstModInt::new(P::PRIME_NUM / i as u32);
37        }
38
39        for i in (0..n - 1).rev() {
40            h[i + 1] = h[i] * invs[i + 1];
41        }
42        h[0] = 0.into();
43
44        Ok(Polynomial::from(h))
45    }
46}
haar_lib/math/fps/log_sparse.rs

haar_lib/math/fps/
log_sparse.rs
