Trait ConvolveSteps

Source

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§

Source

type T

Source

type F

Required Methods§

Source

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

Provided Methods§

Source

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)

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

More examples

Hide additional examples

crates/competitive/src/algorithm/number_of_increasing_sequences_between.rs (line 107)

103    fn mul<C>(&self, other: &Self) -> Self
104    where
105        C: ConvolveSteps<T = Vec<MInt<M>>>,
106    {
107        let c = C::convolve(self.data.clone(), other.data.clone());
108        Self::new(self.offset + other.offset, c)
109    }

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

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

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

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

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

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

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

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