haar_lib/math/fps/
log_sparse.rs

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

haar_lib/math/fps/
log_sparse.rs
