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

haar_lib/math/fps/
inv_sparse.rs
