Struct NTT

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

素数$P$上の数論変換 (Number Theoretic Transform)

PRIM_ROOTはPの原始根。

Implementations

impl<P: PrimeMod> NTT<P>

pub const fn new() -> Self

NTT<P, PRIM_ROOT>を作る。

pub fn ntt(&self, f: &mut [ConstModInt<P>])

数論変換を行う。

pub fn intt(&self, f: &mut [ConstModInt<P>])

nttの逆変換を行う。

pub fn convolve<T>(&self, f: Vec<T>, g: Vec<T>) -> Vec<ConstModInt<P>>

where T: Into<ConstModInt<P>>,

2つのVecを畳み込む。

$(f \ast g)(k) = \sum_{k = i + j} f(i) \times g(j)$

pub fn convolve_same(&self, f: Vec<ConstModInt<P>>) -> Vec<ConstModInt<P>>

convolve(f.clone(), f)と同等。

pub fn max_size(&self) -> usize

NTTで変換可能な配列の最大長を返す。

Trait Implementations

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

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<P: PrimeMod> Default for NTT<P>

fn default() -> Self

Returns the “default value” for a type.