haar_lib/math/fps/
exp_sparse.rs

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

haar_lib/math/fps/
exp_sparse.rs
