Struct Polynomial

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

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

Implementations

impl<P: PrimeMod> 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次だけ低次側にずらす。ただし、負の次数の項は無視する。

pub fn prod(a: Vec<Self>) -> Self

多項式の列の積を計算する。

pub fn pow(self, p: u64) -> Self

多項式の$p$乗を計算する。

pub fn sq(self) -> Self

多項式aの2乗を返す。

pub fn inv(self, n: usize) -> Self

pub fn divrem(self, b: Self) -> (Self, Self)

多項式aの多項式bによる商と剰余を返す。

Trait Implementations

impl<P: PrimeMod> Add for Polynomial<P>

type Output = Polynomial<P>

The resulting type after applying the + operator.

fn add(self, b: Self) -> Self

Performs the + operation.

impl<P: PrimeMod> AddAssign for Polynomial<P>

fn add_assign(&mut self, b: Self)

Performs the += operation.

impl<P: PrimeMod> 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<P: PrimeMod> 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<P: Clone + PrimeMod> Clone for Polynomial<P>

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

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

Formats the value using the given formatter.

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

fn default() -> Polynomial<P>

Returns the “default value” for a type.

impl<P: PrimeMod> Div for Polynomial<P>

type Output = Polynomial<P>

The resulting type after applying the / operator.

fn div(self, rhs: Self) -> Self::Output

Performs the / operation.

impl<P: PrimeMod> DivAssign for Polynomial<P>

fn div_assign(&mut self, rhs: Self)

Performs the /= operation.

impl<P: PrimeMod> FpsExp for Polynomial<P>

type Output = Polynomial<P>

戻り値の型

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

$f(x) = \sum_0^{n-1} a_ix^i$について、$\exp (f(x))$の先頭$n$項を求める。

impl<P: PrimeMod> FpsInv for Polynomial<P>

type Output = Polynomial<P>

戻り値の型

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

$f(x) = \sum_0^{n-1} a_ix^i$について、$\frac{1}{f(x)}$の先頭$n$項を求める。

impl<P: PrimeMod> FpsLog for Polynomial<P>

type Output = Polynomial<P>

戻り値の型

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

$f(x) = \sum_0^{n-1} a_ix^i$について、$\log (f(x))$の先頭$n$項を求める。

impl<P: PrimeMod> FpsPow for Polynomial<P>

type Output = Polynomial<P>

戻り値の型

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

$f(x) = \sum_0^{n-1} a_ix^i$について、$(f(x))^m$の先頭$n$項を求める。

impl<P: PrimeMod> FpsSqrt for Polynomial<P>

type Output = Polynomial<P>

戻り値の型

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

$f(x) = \sum_0^{n-1} a_ix^i$について、$\sqrt{f(x)}$の先頭$n$項を求める。

impl<P: PrimeMod> From<Polynomial<P>> for Vec<ConstModInt<P>>

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

Converts to this type from the input type.

impl<T, P: PrimeMod> 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<P: PrimeMod> 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<P: PrimeMod> IndexMut<usize> for Polynomial<P>

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

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

impl<P: PrimeMod> Mul for Polynomial<P>

type Output = Polynomial<P>

The resulting type after applying the * operator.

fn mul(self, rhs: Self) -> Self::Output

Performs the * operation.

impl<P: PrimeMod> MulAssign for Polynomial<P>

fn mul_assign(&mut self, rhs: Self)

Performs the *= operation.

impl<P: PrimeMod> MultipointEval for Polynomial<P>

type Value = ConstModInt<P>

多項式の係数の型

fn multipoint_eval(self, p: Vec<Self::Value>) -> Vec<Self::Value>

多項式の多点評価

impl<P: PrimeMod> 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<P: PrimeMod> Rem for Polynomial<P>

type Output = Polynomial<P>

The resulting type after applying the % operator.

fn rem(self, rhs: Self) -> Self::Output

Performs the % operation.

impl<P: PrimeMod> RemAssign for Polynomial<P>

fn rem_assign(&mut self, rhs: Self)

Performs the %= operation.

impl<P: PrimeMod> Sub for Polynomial<P>

type Output = Polynomial<P>

The resulting type after applying the - operator.

fn sub(self, b: Self) -> Self

Performs the - operation.

impl<P: PrimeMod> SubAssign for Polynomial<P>

fn sub_assign(&mut self, b: Self)

Performs the -= operation.

impl<P: PrimeMod> TaylorShift for Polynomial<P>

type Value = ConstModInt<P>

多項式の係数の型

fn taylor_shift(self, c: Self::Value) -> Self

多項式 p = $f(x) = a_0 + a_1x + \cdots + a_nx^n$に対して、
多項式 $f(x + c) = a_0 + a_1(x + c) + \cdots + a_n(x + c)^n = b_0 + b_0x + \cdots + b_nx^n$ を満たす、数列{$b_i$}を求める。

impl<P: PrimeMod> Eq for Polynomial<P>