Struct SparsePolynomial

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

疎な多項式

Implementations

impl<const P: u32> SparsePolynomial<P>

pub fn zero() -> Self

零多項式を得る。

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

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

pub fn add(&mut self, i: usize, x: ConstModInt<P>)

pub fn from_vec(a: Vec<(usize, ConstModInt<P>)>) -> Self

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次だけ高次側にずらす。

Trait Implementations

impl<const P: u32> Clone for SparsePolynomial<P>

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

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<const P: u32> Debug for SparsePolynomial<P>

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

Formats the value using the given formatter.

impl<const P: u32> Default for SparsePolynomial<P>

fn default() -> SparsePolynomial<P>

Returns the “default value” for a type.

impl<const P: u32> 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<const P: u32> 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<const P: u32> 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<const P: u32> 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<const P: u32> FpsSqrtSparse for SparsePolynomial<P>

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

Time complexity $O(nk)$

type Output = Polynomial<P>

戻り値の型