Struct SparsePolynomial

pub struct SparsePolynomial<P: PrimeMod> { /* private fields */ }

疎な多項式

Implementations

impl<P: PrimeMod> SparsePolynomial<P>

pub fn zero() -> Self

零多項式を得る。

pub fn constant(a: ConstModInt<P>) -> Self

定数項のみをもつ多項式を生成する。

pub fn add_one_term<T>(&mut self, i: usize, k: T)

where ConstModInt<P>: From<T>,

$k x^i$となる項を足す。

pub fn coeff_of(&self, i: usize) -> ConstModInt<P>

$x^i$の係数を得る。

pub fn differential(&mut self)

多項式を微分する。

pub fn integral(&mut self)

多項式を積分する。

pub fn scale(&mut self, k: ConstModInt<P>)

多項式をk倍する。

pub fn shift_lower(&mut self, k: usize)

係数をk次だけ低次側にずらす。ただし、負の次数の項は無視する。

pub fn shift_higher(&mut self, k: usize)

係数をk次だけ高次側にずらす。

pub fn iter(&self) -> impl Iterator<Item = (&usize, &ConstModInt<P>)>

項の次数と係数のペアへのイテレータを返す。

Trait Implementations

impl<P: Clone + PrimeMod> Clone for SparsePolynomial<P>

fn clone(&self) -> SparsePolynomial<P>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<P: Debug + PrimeMod> Debug for SparsePolynomial<P>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<P: Default + PrimeMod> Default for SparsePolynomial<P>

fn default() -> SparsePolynomial<P>

Returns the “default value” for a type.

impl<P: PrimeMod> FpsExpSparse for SparsePolynomial<P>

fn fps_exp_sparse(self, n: usize) -> Result<Self::Output, &'static str>

Time complexity $O(nk)$

type Output = Polynomial<P>

戻り値の型

impl<P: PrimeMod> FpsInvSparse for SparsePolynomial<P>

fn fps_inv_sparse(self, n: usize) -> Result<Self::Output, &'static str>

Time complexity $O(nk)$

type Output = Polynomial<P>

戻り値の型

impl<P: PrimeMod> FpsLogSparse for SparsePolynomial<P>

fn fps_log_sparse(self, n: usize) -> Result<Self::Output, &'static str>

Time complexity $O(nk)$

type Output = Polynomial<P>

戻り値の型

impl<P: PrimeMod> FpsPowSparse for SparsePolynomial<P>

fn fps_pow_sparse(self, m: u64, n: usize) -> Result<Self::Output, &'static str>

Time complexity $O(nk)$

type Output = Polynomial<P>

戻り値の型

impl<P: PrimeMod> FpsSqrtSparse for SparsePolynomial<P>

fn fps_sqrt_sparse(self, n: usize) -> Result<Self::Output, &'static str>

Time complexity $O(nk)$

type Output = Polynomial<P>

戻り値の型

impl<P: PrimeMod, T> From<Vec<(usize, T)>> for SparsePolynomial<P>

where ConstModInt<P>: From<T>,

fn from(value: Vec<(usize, T)>) -> Self

Converts to this type from the input type.