Struct GcdConvolve

pub struct GcdConvolve<M> { /* private fields */ }

Implementations

impl<M> GcdConvolve<M>

where M: Monoid,

pub fn zeta_transform(f: &mut [M::T])

$$g(m) = \sum_{n \mid m}f(n)$$

Examples found in repository

crates/competitive/src/math/gcd_convolve.rs (line 55)

    fn transform(mut t: Self::T, _len: usize) -> Self::F {
        GcdConvolve::<R::Additive>::zeta_transform(&mut t);
        t
    }

impl<G> GcdConvolve<G>

where G: Group,

pub fn mobius_transform(f: &mut [G::T])

$$f(m) = \sum_{n \mid m}h(n)$$

Examples found in repository

crates/competitive/src/math/gcd_convolve.rs (line 60)

    fn inverse_transform(mut f: Self::F, _len: usize) -> Self::T {
        GcdConvolve::<R::Additive>::mobius_transform(&mut f);
        f
    }

Trait Implementations

impl<R> ConvolveSteps for GcdConvolve<R>

where R: Ring, R::Additive: Invertible,

type T = Vec<<R as SemiRing>::T>

type F = Vec<<R as SemiRing>::T>

fn length(t: &Self::T) -> usize

fn transform(t: Self::T, _len: usize) -> Self::F

fn inverse_transform(f: Self::F, _len: usize) -> Self::T

fn multiply(f: &mut Self::F, g: &Self::F)

fn convolve(a: Self::T, b: Self::T) -> Self::T