Trait ConvolveSteps

Source

pub trait ConvolveSteps {
    type T;
    type F;

    const CYCLIC: bool = false;

    // 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 square(t: Self::T, len: usize) -> Self::T
       where Self::T: Clone { ... }
    fn convolve(a: Self::T, b: Self::T) -> Self::T { ... }
}

Provided Associated Constants§

Source

const CYCLIC: bool = false

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

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 square(t: Self::T, len: usize) -> Self::T
where Self::T: Clone,

Examples found in repository ?

crates/competitive/src/math/formal_power_series/formal_power_series_impls.rs (line 934)

883    pub fn sqrt(&self, deg: usize) -> Option<Self> {
884        if self[0].is_zero() {
885            if let Some(k) = self.iter().position(|x| !x.is_zero()) {
886                if k % 2 != 0 {
887                    return None;
888                } else if deg > k / 2 {
889                    return Some((self >> k).sqrt(deg - k / 2)? << (k / 2));
890                }
891            }
892        } else {
893            let s = self[0].sqrt_coefficient()?;
894            if deg <= 1 {
895                return Some(Self::from(s).prefix(deg));
896            }
897            if let Some(step) = self.sparse_stride(deg, 4) {
898                let t = self[0].clone();
899                let mut f = self.prefix_ref(deg) / t;
900                f = f.pow_sparse1(T::one() / T::from(2usize), deg, step);
901                f *= s;
902                return Some(f);
903            }
904
905            let mut f = Self::from(s);
906            let inv2 = T::one() / (T::one() + T::one());
907            let inv2s = inv2.clone() / &f[0];
908            let extend = |f: &mut Self, end| {
909                for i in f.length()..end {
910                    let mut value = self.coeff(i);
911                    for j in 1..i {
912                        value -= f[j].clone() * &f[i - j];
913                    }
914                    f.data.push(value * &inv2s);
915                }
916            };
917            extend(&mut f, deg.min(32));
918            f.truncate(deg);
919            if f.length() == deg {
920                return Some(f);
921            }
922            let mut inverse = f.inv(f.length());
923            let mut i = f.length();
924            while i < deg {
925                if deg - i <= 4 {
926                    extend(&mut f, deg);
927                    break;
928                }
929                let len = (i * 2).min(deg);
930                let factor = C::transform(inverse.data.clone(), i * 2);
931                let error = if !C::CYCLIC || i < 128 {
932                    (self.prefix_ref(len) - &f * &f) >> i
933                } else {
934                    let square = C::square(f.data.clone(), i);
935                    // The cyclic square folds its high half into the already known low half.
936                    Self::from_vec(
937                        square
938                            .into_iter()
939                            .take(len - i)
940                            .enumerate()
941                            .map(|(j, value)| self.coeff(i + j) + self.coeff(j) - value)
942                            .collect(),
943                    )
944                };
945                let mut error_fft = C::transform(error.data, i * 2);
946                C::multiply(&mut error_fft, &factor);
947                let delta = C::inverse_transform(error_fft, i * 2);
948                f.data
949                    .extend(delta.into_iter().take(len - i).map(|x| x * &inv2));
950                if i * 2 + 4 < deg {
951                    let mut error_fft = C::transform(f.data.clone(), i * 2);
952                    C::multiply(&mut error_fft, &factor);
953                    let error = C::inverse_transform(error_fft, i * 2);
954                    let mut error_fft = C::transform(error.into_iter().skip(i).collect(), i * 2);
955                    C::multiply(&mut error_fft, &factor);
956                    let error = C::inverse_transform(error_fft, i * 2);
957                    inverse.data.extend(error.into_iter().take(i).map(Neg::neg));
958                }
959                i *= 2;
960            }
961            f.truncate(deg);
962            return Some(f);
963        }
964        Some(Self::zeros(deg))
965    }

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/library_checker/src/convolution/convolution_mod.rs (line 11)

8pub fn convolution_mod(reader: impl Read, writer: impl Write) {
9    prepare_io!(reader, writer);
10    sc!(n, m, a: [M; n], b: [M; m]);
11    let c = Convolve998244353::convolve(a, b);
12    pp!(@it c);
13}

crates/library_checker/src/convolution/convolution_mod_2_64.rs (line 8)

5pub fn convolution_mod_2_64(reader: impl Read, writer: impl Write) {
6    prepare_io!(reader, writer);
7    sc!(n, m, a: [u64; n], b: [u64; m]);
8    let c = U64Convolve::convolve(a, b);
9    pp!(@it c);
10}

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

11pub fn convolution_mod_large(reader: impl Read, writer: impl Write) {
12    prepare_io!(reader, writer);
13    sc!(n, m, a: [M; n], b: [M; m]);
14    let c = Convolve998244353::convolve(a, b);
15    pp!(@it c);
16}

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/library_checker/src/set_power_series/subset_convolution.rs (line 12)

9pub fn subset_convolution(reader: impl Read, writer: impl Write) {
10    prepare_io!(reader, writer);
11    sc!(n, a: [M; 1 << n], b: [M; 1 << n]);
12    let c = SubsetConvolve::<AddMulOperation<_>>::convolve(a, b);
13    pp!(@it c);
14}