Struct BitwisexorConvolve 

pub struct BitwisexorConvolve<M, const EXACT_DIVISION: bool = false> {
    _marker: PhantomData<fn() -> M>,
}

EXACT_DIVISION normalizes with division instead of a multiplicative inverse.

Fields

_marker: PhantomData<fn() -> M>

Implementations

impl<G, const EXACT_DIVISION: bool> BitwisexorConvolve<G, EXACT_DIVISION>

where G: Group,

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

Examples found in repository

crates/competitive/src/math/bitwisexor_convolve.rs (line 61)

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

    fn inverse_transform(mut f: Self::F, len: usize) -> Self::T {
        BitwisexorConvolve::<R::Additive, EXACT_DIVISION>::hadamard_transform(&mut f);
        let len = R::T::from_length(len);
        if EXACT_DIVISION {
            for f in &mut f {
                *f = R::div(f, &len);
            }
        } else if !f.is_empty() {
            let inv_len = R::inv(&len);
            for f in &mut f {
                *f = R::mul(f, &inv_len);
            }
        }
        f
    }

Trait Implementations

impl<R, const EXACT_DIVISION: bool> ConvolveSteps for BitwisexorConvolve<R, EXACT_DIVISION>

where R: Field<T: PartialEq + FromLength<EXACT_DIVISION>, Additive: Invertible, Multiplicative: 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

const CYCLIC: bool = false

Whether transform multiplication computes modulo x^n - 1 in the coefficient ring.

fn square(t: Self::T, len: usize) -> Self::T

where Self::T: Clone,