Struct Polynomial

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

$\mathbb{F}_p$上の多項式

Implementations

impl<const P: u32> Polynomial<P>

pub fn zero() -> Self

零多項式を得る。

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

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

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

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

pub fn eval(&self, p: ConstModInt<P>) -> ConstModInt<P>

多項式に値pを代入した結果を求める。

pub fn len(&self) -> usize

内部のVecの長さを返す。

pub fn is_empty(&self) -> bool

項数が0のときtrueを返す。

pub fn shrink(&mut self)

係数が0の高次項を縮める。

pub fn get_until(&self, t: usize) -> Self

len()を超えないように、先頭t項をもつ多項式を返す。

pub fn deg(&self) -> Option<usize>

多項式の次数を返す。

selfが零多項式のときはNoneを返す。

Time complexity $O(n)$

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

多項式をk倍する。

pub fn differentiate(&mut self)

多項式を微分する。

pub fn integrate(&mut self)

多項式を積分する。

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

係数をk次だけ高次側にずらす。ただし、$x^n$の項以降は無視する。

$(a_0 + a_1 x + a_2 x^2 + \ldots + a_{n-1} x^{n-1}) \times x^k \pmod {x^n}$

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

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

Trait Implementations

impl<const P: u32> Add for Polynomial<P>

type Output = Polynomial<P>

The resulting type after applying the + operator.

fn add(self, b: Polynomial<P>) -> Polynomial<P>

Performs the + operation.

impl<const P: u32> AddAssign for Polynomial<P>

fn add_assign(&mut self, b: Polynomial<P>)

Performs the += operation.

impl<const P: u32> AsMut<Vec<ConstModInt<P>>> for Polynomial<P>

fn as_mut(&mut self) -> &mut Vec<ConstModInt<P>>

Converts this type into a mutable reference of the (usually inferred) input type.

impl<const P: u32> AsRef<[ConstModInt<P>]> for Polynomial<P>

fn as_ref(&self) -> &[ConstModInt<P>]

Converts this type into a shared reference of the (usually inferred) input type.

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

fn clone(&self) -> Polynomial<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 Polynomial<P>

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

Formats the value using the given formatter.

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

fn default() -> Polynomial<P>

Returns the “default value” for a type.

impl<const P: u32> From<Polynomial<P>> for Vec<ConstModInt<P>>

fn from(value: Polynomial<P>) -> Self

Converts to this type from the input type.

impl<T, const P: u32> From<Vec<T>> for Polynomial<P>

where T: Into<ConstModInt<P>>,

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

Converts to this type from the input type.

impl<const P: u32> Index<usize> for Polynomial<P>

type Output = ConstModInt<P>

The returned type after indexing.

fn index(&self, index: usize) -> &Self::Output

Performs the indexing (container[index]) operation.

impl<const P: u32> IndexMut<usize> for Polynomial<P>

fn index_mut(&mut self, index: usize) -> &mut Self::Output

Performs the mutable indexing (container[index]) operation.

impl<const P: u32> PartialEq for Polynomial<P>

fn eq(&self, other: &Self) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<const P: u32> Sub for Polynomial<P>

type Output = Polynomial<P>

The resulting type after applying the - operator.

fn sub(self, b: Polynomial<P>) -> Polynomial<P>

Performs the - operation.

impl<const P: u32> SubAssign for Polynomial<P>

fn sub_assign(&mut self, b: Polynomial<P>)

Performs the -= operation.