Struct BitwiseorConvolve

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

Implementations

impl<M> BitwiseorConvolve<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/bitwiseor_convolve.rs (line 42)

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

crates/competitive/src/math/subset_convolve.rs (line 29)

    fn transform(t: Self::T, len: usize) -> Self::F {
        let k = len.trailing_zeros() as usize;
        let mut f = vec![vec![R::zero(); len]; k + 1];
        for (i, t) in t.iter().enumerate() {
            let f = &mut f[i.count_ones() as usize][i];
            *f = R::add(f, t);
        }
        for f in f.iter_mut() {
            BitwiseorConvolve::<R::Additive>::zeta_transform(f);
        }
        f
    }

impl<G> BitwiseorConvolve<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/bitwiseor_convolve.rs (line 47)

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

crates/competitive/src/math/subset_convolve.rs (line 36)

    fn inverse_transform(mut f: Self::F, len: usize) -> Self::T {
        for f in f.iter_mut() {
            BitwiseorConvolve::<R::Additive>::mobius_transform(f);
        }
        let mut t = vec![R::zero(); len];
        for (i, t) in t.iter_mut().enumerate() {
            *t = R::add(t, &f[i.count_ones() as usize][i]);
        }
        t
    }

Trait Implementations

impl<R> ConvolveSteps for BitwiseorConvolve<R>

where R: Ring, R::T: PartialEq, 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