competitive/math/convolve_steps.rs
1pub trait ConvolveSteps {
2 type T;
3 type F;
4 fn length(t: &Self::T) -> usize;
5 fn transform(t: Self::T, len: usize) -> Self::F;
6 fn inverse_transform(f: Self::F, len: usize) -> Self::T;
7 fn multiply(f: &mut Self::F, g: &Self::F);
8 fn convolve(a: Self::T, b: Self::T) -> Self::T {
9 let len = (Self::length(&a) + Self::length(&b)).saturating_sub(1);
10 let mut a = Self::transform(a, len);
11 let b = Self::transform(b, len);
12 Self::multiply(&mut a, &b);
13 Self::inverse_transform(a, len)
14 }
15}