haar_lib/math/fps/
inv_sparse.rs

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

haar_lib/math/fps/
inv_sparse.rs
