competitive/math/
convolve_steps.rs

1pub trait ConvolveSteps {
2    /// Whether transform multiplication computes modulo x^n - 1 in the coefficient ring.
3    const CYCLIC: bool = false;
4
5    type T;
6    type F;
7    fn length(t: &Self::T) -> usize;
8    fn transform(t: Self::T, len: usize) -> Self::F;
9    fn inverse_transform(f: Self::F, len: usize) -> Self::T;
10    fn multiply(f: &mut Self::F, g: &Self::F);
11    fn square(t: Self::T, len: usize) -> Self::T
12    where
13        Self::T: Clone,
14    {
15        let mut f = Self::transform(t.clone(), len);
16        let g = Self::transform(t, len);
17        Self::multiply(&mut f, &g);
18        Self::inverse_transform(f, len)
19    }
20    fn convolve(a: Self::T, b: Self::T) -> Self::T {
21        let len = (Self::length(&a) + Self::length(&b)).saturating_sub(1);
22        let mut a = Self::transform(a, len);
23        let b = Self::transform(b, len);
24        Self::multiply(&mut a, &b);
25        Self::inverse_transform(a, len)
26    }
27}
competitive/math/convolve_steps.rs

competitive/math/
convolve_steps.rs
