haar_lib/math/fps/
exp.rs

1//! 形式的冪級数の指数関数
2use crate::math::fps::log::*;
3use crate::math::polynomial::Polynomial;
4use crate::math::prime_mod::PrimeMod;
5
6/// 形式的冪級数の指数関数
7pub trait FpsExp {
8    /// 戻り値の型
9    type Output;
10
11    /// $f(x) = \sum_0^{n-1} a_ix^i$について、$\exp (f(x))$の先頭$n$項を求める。
12    fn fps_exp(self) -> Result<Self::Output, &'static str>;
13}
14
15impl<P: PrimeMod> FpsExp for Polynomial<P> {
16    type Output = Self;
17
18    fn fps_exp(self) -> Result<Self::Output, &'static str> {
19        let f: Vec<_> = self.into();
20        let n = f.len();
21
22        let mut t = 1;
23        let mut b = Self::constant(1.into());
24
25        loop {
26            let mut temp: Vec<_> = b.clone().fps_log()?.into();
27
28            temp.resize(2 * t, 0.into());
29            temp.iter_mut().for_each(|x| *x = -*x);
30            temp[0] += 1.into();
31
32            temp.iter_mut()
33                .zip(f.iter())
34                .for_each(|(temp, f)| *temp += *f);
35
36            b *= temp.into();
37            b.as_mut().resize(2 * t, 0.into());
38
39            if t >= n {
40                break;
41            }
42
43            t <<= 1;
44        }
45
46        b.as_mut().truncate(n);
47        Ok(b)
48    }
49}
haar_lib/math/fps/exp.rs

haar_lib/math/fps/
exp.rs
