Struct NTT

pub struct NTT<const P: u32, const PRIM_ROOT: u32> { /* private fields */ }

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

PRIM_ROOTはPの原始根。

Implementations

impl<const P: u32, const PRIM_ROOT: u32> NTT<P, PRIM_ROOT>

pub fn new() -> Self

NTT<P, PRIM_ROOT>を作る。

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

数論変換を行う。

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

nttの逆変換を行う。

pub fn convolve( &self, f: Vec<ConstModInt<P>>, g: Vec<ConstModInt<P>>, ) -> Vec<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<const P: u32, const PRIM_ROOT: u32> Default for NTT<P, PRIM_ROOT>

fn default() -> Self

Returns the “default value” for a type.