Trait ConvolveSteps 

pub trait ConvolveSteps {
    type T;
    type F;

    // Required methods
    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);

    // Provided method
    fn convolve(a: Self::T, b: Self::T) -> Self::T { ... }
}

Required Associated Types

type T

type F

Required Methods

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)

Provided Methods

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

Examples found in repository

crates/competitive/src/math/formal_power_series/formal_power_series_nums.rs (line 200)

    fn mul(self, rhs: Self) -> Self::Output {
        Self::from_vec(C::convolve(self.data, rhs.data))
    }

crates/competitive/src/math/relaxed_convolution.rs (line 75)

    fn calc_block(&mut self, la: usize, lb: usize, size: usize) {
        let a = self.a[la..la + size].to_vec();
        let b = self.b[lb..lb + size].to_vec();
        let c = C::convolve(a, b);
        for (c, d) in zip(c, &mut self.c[la + lb..]) {
            *d += c;
        }
    }

crates/library_checker/src/convolution/convolution_mod.rs (line 13)

pub fn convolution_mod(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, m, a: [MInt998244353; n], b: [MInt998244353; m]);
    let c = Convolve998244353::convolve(a, b);
    iter_print!(writer, @it c);
}

crates/library_checker/src/set_power_series/subset_convolution.rs (line 14)

pub fn subset_convolution(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, a: [MInt998244353; 1 << n], b: [MInt998244353; 1 << n]);
    let c = SubsetConvolve::<AddMulOperation<_>>::convolve(a, b);
    iter_print!(writer, @it c);
}

crates/library_checker/src/convolution/convolution_mod_1000000007.rs (line 14)

pub fn convolution_mod_1000000007(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    type M = MInt1000000007;
    scan!(scanner, n, m, a: [M; n], b: [M; m]);
    let c = MIntConvolve::<Modulo1000000007>::convolve(a, b);
    iter_print!(writer, @it c);
}

crates/library_checker/src/convolution/bitwise_and_convolution.rs (line 14)

pub fn bitwise_and_convolution(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, a: [MInt998244353; 1 << n], b: [MInt998244353; 1 << n]);
    let c = BitwiseandConvolve::<AddMulOperation<_>>::convolve(a, b);
    iter_print!(writer, @it c);
}

#[verify::library_checker("bitwise_and_convolution")]
pub fn bitwise_or_convolution(reader: impl Read, mut writer: impl Write) {
    let s = read_all_unchecked(reader);
    let mut scanner = Scanner::new(&s);
    scan!(scanner, n, mut a: [MInt998244353; 1 << n], mut b: [MInt998244353; 1 << n]);
    a.reverse();
    b.reverse();
    let mut c = BitwiseorConvolve::<AddMulOperation<_>>::convolve(a, b);
    c.reverse();
    iter_print!(writer, @it c);
}

Additional examples can be found in:

• crates/library_checker/src/convolution/gcd_convolution.rs
• crates/library_checker/src/convolution/lcm_convolution.rs
• crates/competitive/src/tree/centroid_decomposition.rs
• crates/competitive/src/math/number_theoretic_transform.rs

Dyn Compatibility

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors

impl ConvolveSteps for ConvolveRealFft

type T = Vec<i64>

type F = Vec<Complex<f64>>

impl<M> ConvolveSteps for Convolve<M>

where M: Montgomery32NttModulus,

type T = Vec<MInt<M>>

type F = Vec<MInt<M>>

impl<M, N1, N2, N3> ConvolveSteps for Convolve<(M, (N1, N2, N3))>

where M: MIntConvert + MIntConvert<u32>, N1: Montgomery32NttModulus, N2: Montgomery32NttModulus, N3: Montgomery32NttModulus,

type T = Vec<MInt<M>>

type F = (Vec<MInt<N1>>, Vec<MInt<N2>>, Vec<MInt<N3>>)

impl<N1, N2, N3> ConvolveSteps for Convolve<(u64, (N1, N2, N3))>

where N1: Montgomery32NttModulus, N2: Montgomery32NttModulus, N3: Montgomery32NttModulus,

type T = Vec<u64>

type F = (Vec<MInt<N1>>, Vec<MInt<N2>>, Vec<MInt<N3>>)

impl<R> ConvolveSteps for BitwiseandConvolve<R>

where R: Ring<T: PartialEq, Additive: Invertible>,

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

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

impl<R> ConvolveSteps for BitwiseorConvolve<R>

where R: Ring<T: PartialEq, Additive: Invertible>,

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

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

impl<R> ConvolveSteps for BitwisexorConvolve<R, false>

where R: Field<T: PartialEq + From<usize>, Additive: Invertible, Multiplicative: Invertible>,

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

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

impl<R> ConvolveSteps for BitwisexorConvolve<R, true>

where R: Field<T: PartialEq + TryFrom<usize>, Additive: Invertible, Multiplicative: Invertible>, <R::T as TryFrom<usize>>::Error: Debug,

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

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

impl<R> ConvolveSteps for GcdConvolve<R>

where R: Ring<Additive: Invertible>,

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

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

impl<R> ConvolveSteps for LcmConvolve<R>

where R: Ring<Additive: Invertible>,

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

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

impl<R> ConvolveSteps for SubsetConvolve<R>

where R: Ring<T: PartialEq, Additive: Invertible>,

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

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