Struct PolynomialOperator

pub struct PolynomialOperator<'a, const P: u32, const PR: u32> { /* private fields */ }

多項式の演算を扱う。

Implementations

impl<'a, const P: u32, const PR: u32> PolynomialOperator<'a, P, PR>

pub fn new(ntt: &'a NTT<P, PR>) -> Self

NTT<P>を基にPolynomialOperator<P>を生成する。

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

多項式aに多項式bを足す。

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

多項式aと多項式bの和を返す。

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

多項式aから多項式bを引く。

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

多項式aと多項式bの差を返す。

pub fn mul_assign(&self, a: &mut Polynomial<P>, b: Polynomial<P>)

多項式aに多項式bを掛ける。

pub fn mul(&self, a: Polynomial<P>, b: Polynomial<P>) -> Polynomial<P>

多項式aと多項式bの積を返す。

pub fn sq(&self, a: Polynomial<P>) -> Polynomial<P>

多項式aの2乗を返す。

pub fn scale(&self, a: Polynomial<P>, k: ConstModInt<P>) -> Polynomial<P>

多項式aのk倍を返す。

pub fn inv(&self, a: Polynomial<P>, n: usize) -> Polynomial<P>

pub fn divmod( &self, a: Polynomial<P>, b: Polynomial<P>, ) -> (Polynomial<P>, Polynomial<P>)

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

pub fn differentiate(&self, a: Polynomial<P>) -> Polynomial<P>

多項式の微分を返す。

pub fn integrate(&self, a: Polynomial<P>) -> Polynomial<P>

多項式の積分を返す。

pub fn shift_higher(&self, a: Polynomial<P>, k: usize) -> Polynomial<P>

係数を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(&self, a: Polynomial<P>, k: usize) -> Polynomial<P>

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

Trait Implementations

impl<const P: u32, const PR: u32> FpsExp for PolynomialOperator<'_, P, PR>

type Poly = Polynomial<P>

多項式の型

fn fps_exp(&self, f: Self::Poly) -> Self::Poly

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

impl<const P: u32, const PR: u32> FpsInv for PolynomialOperator<'_, P, PR>

type Poly = Polynomial<P>

多項式の型

fn fps_inv(&self, f: Self::Poly) -> Self::Poly

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

impl<const P: u32, const PR: u32> FpsLog for PolynomialOperator<'_, P, PR>

type Poly = Polynomial<P>

多項式の型

fn fps_log(&self, f: Self::Poly) -> Self::Poly

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

impl<const P: u32, const PR: u32> FpsPow for PolynomialOperator<'_, P, PR>

type Poly = Polynomial<P>

多項式の型

fn fps_pow(&self, f: Self::Poly, m: u64) -> Self::Poly

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

impl<const P: u32, const PR: u32> FpsSqrt for PolynomialOperator<'_, P, PR>

type Poly = Polynomial<P>

多項式の型

fn fps_sqrt(&self, f: Self::Poly) -> Option<Self::Poly>

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

impl<const P: u32, const PR: u32> MultipointEval for PolynomialOperator<'_, P, PR>

type Poly = Polynomial<P>

多項式の型

type Value = ConstModInt<P>

多項式の係数の型

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

多項式の多点評価

impl<const P: u32, const PR: u32> TaylorShift for PolynomialOperator<'_, P, PR>

type Poly = Polynomial<P>

多項式の型

type Value = ConstModInt<P>

多項式の係数の型

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

多項式 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$}を求める。