haar_lib/math/fps/
exp_sparse.rs

1//! 疎な形式的冪級数の指数関数
2use crate::math::polynomial::Polynomial;
3use crate::math::sparse_polynomial::SparsePolynomial;
4use crate::num::const_modint::*;
5
6/// 疎な形式的冪級数の指数関数
7pub trait FpsExpSparse {
8    /// 戻り値の型
9    type Output;
10
11    /// $f(x) = \sum_0^{n-1} a_ix^i$について、$\exp (f(x))$の先頭$n$項を求める。
12    fn fps_exp_sparse(self, n: usize) -> Result<Self::Output, &'static str>;
13}
14
15impl<const P: u32> FpsExpSparse for SparsePolynomial<P> {
16    type Output = Polynomial<P>;
17
18    /// **Time complexity** $O(nk)$
19    fn fps_exp_sparse(self, n: usize) -> Result<Self::Output, &'static str> {
20        if self.coeff_of(0).value() != 0 {
21            return Err("定数項が`0`の形式的べき級数のexpを計算しようとした。");
22        }
23
24        let mut f = self;
25        f.differential();
26
27        let mut g = vec![ConstModInt::new(0); n];
28        g[0] = 1.into();
29
30        let mut invs = vec![ConstModInt::new(1); n + 1];
31        for i in 2..=n {
32            invs[i] = -invs[P as usize % i] * ConstModInt::new(P / i as u32);
33        }
34
35        for i in 0..n - 1 {
36            let mut s = ConstModInt::new(0);
37            for &(j, fj) in f.data.iter() {
38                if i >= j {
39                    s += fj * g[i - j];
40                }
41            }
42
43            g[i + 1] = s * invs[i + 1];
44        }
45
46        Ok(Polynomial::from(g))
47    }
48}
haar_lib/math/fps/exp_sparse.rs

haar_lib/math/fps/
exp_sparse.rs
