Struct FloorSum 

struct FloorSum<R, const X: usize, const Y: usize>
where
    R: SemiRing,
{
    _marker: PhantomData<fn() -> R>,
}

Fields

_marker: PhantomData<fn() -> R>

Implementations

impl<R, const X: usize, const Y: usize> FloorSum<R, X, Y>

where R: SemiRing,

fn to_x() -> FloorSumData<R, X, Y>

Examples found in repository

crates/competitive/src/math/floor_sum.rs (line 289)

pub fn floor_sum_polynomial<T, const X: usize, const Y: usize>(
    n: u64,
    a: u64,
    b: u64,
    m: u64,
) -> [[T; Y]; X]
where
    T: Clone + Zero + One + Add<Output = T> + Mul<Output = T>,
{
    debug_assert!(a == 0 || n < (u64::MAX - b) / a);
    floor_monoid_product::<FloorSum<AddMulOperation<T>, X, Y>>(
        FloorSum::<AddMulOperation<T>, X, Y>::to_x(),
        FloorSum::<AddMulOperation<T>, X, Y>::to_y(),
        n,
        a,
        b,
        m,
    )
    .dp
}

/// $$\sum_{i=l}^{r-1}i^X\left\lfloor\frac{a\times i+b}{m}\right\rfloor^Y$$
pub fn floor_sum_polynomial_i64<T, const X: usize, const Y: usize>(
    l: i64,
    r: i64,
    a: i64,
    b: i64,
    m: u64,
) -> [[T; Y]; X]
where
    T: Clone + Zero + One + Add<Output = T> + Mul<Output = T>,
    AddMulOperation<T>: SemiRing<T = T, Additive: Invertible>,
{
    assert!(l <= r);
    assert!(m > 0);

    if a < 0 {
        let mut ans = floor_sum_polynomial_i64::<T, X, Y>(-r + 1, -l + 1, -a, b, m);
        for ans in ans.iter_mut().skip(1).step_by(2) {
            for ans in ans.iter_mut() {
                *ans = AddMulOperation::<T>::neg(ans);
            }
        }
        return ans;
    }

    let add_x = l;
    let n = (r - l) as u64;
    let b = a * add_x + b;

    let add_y = b.div_euclid(m as i64);
    let b = b.rem_euclid(m as i64);
    assert!(a >= 0);
    assert!(b >= 0);
    let data = floor_monoid_product::<FloorSum<AddMulOperation<T>, X, Y>>(
        FloorSum::<AddMulOperation<T>, X, Y>::to_x(),
        FloorSum::<AddMulOperation<T>, X, Y>::to_y(),
        n,
        a as u64,
        b as u64,
        m,
    );

    let offset = FloorSum::<AddMulOperation<T>, X, Y>::offset(add_x, add_y);
    FloorSum::<AddMulOperation<T>, X, Y>::operate(&offset, &data).dp
}

fn to_y() -> FloorSumData<R, X, Y>

Examples found in repository

crates/competitive/src/math/floor_sum.rs (line 290)

pub fn floor_sum_polynomial<T, const X: usize, const Y: usize>(
    n: u64,
    a: u64,
    b: u64,
    m: u64,
) -> [[T; Y]; X]
where
    T: Clone + Zero + One + Add<Output = T> + Mul<Output = T>,
{
    debug_assert!(a == 0 || n < (u64::MAX - b) / a);
    floor_monoid_product::<FloorSum<AddMulOperation<T>, X, Y>>(
        FloorSum::<AddMulOperation<T>, X, Y>::to_x(),
        FloorSum::<AddMulOperation<T>, X, Y>::to_y(),
        n,
        a,
        b,
        m,
    )
    .dp
}

/// $$\sum_{i=l}^{r-1}i^X\left\lfloor\frac{a\times i+b}{m}\right\rfloor^Y$$
pub fn floor_sum_polynomial_i64<T, const X: usize, const Y: usize>(
    l: i64,
    r: i64,
    a: i64,
    b: i64,
    m: u64,
) -> [[T; Y]; X]
where
    T: Clone + Zero + One + Add<Output = T> + Mul<Output = T>,
    AddMulOperation<T>: SemiRing<T = T, Additive: Invertible>,
{
    assert!(l <= r);
    assert!(m > 0);

    if a < 0 {
        let mut ans = floor_sum_polynomial_i64::<T, X, Y>(-r + 1, -l + 1, -a, b, m);
        for ans in ans.iter_mut().skip(1).step_by(2) {
            for ans in ans.iter_mut() {
                *ans = AddMulOperation::<T>::neg(ans);
            }
        }
        return ans;
    }

    let add_x = l;
    let n = (r - l) as u64;
    let b = a * add_x + b;

    let add_y = b.div_euclid(m as i64);
    let b = b.rem_euclid(m as i64);
    assert!(a >= 0);
    assert!(b >= 0);
    let data = floor_monoid_product::<FloorSum<AddMulOperation<T>, X, Y>>(
        FloorSum::<AddMulOperation<T>, X, Y>::to_x(),
        FloorSum::<AddMulOperation<T>, X, Y>::to_y(),
        n,
        a as u64,
        b as u64,
        m,
    );

    let offset = FloorSum::<AddMulOperation<T>, X, Y>::offset(add_x, add_y);
    FloorSum::<AddMulOperation<T>, X, Y>::operate(&offset, &data).dp
}

impl<R, const X: usize, const Y: usize> FloorSum<R, X, Y>

where R: Ring<Additive: Invertible>,

fn offset(x: i64, y: i64) -> FloorSumData<R, X, Y>

Examples found in repository

crates/competitive/src/math/floor_sum.rs (line 341)

pub fn floor_sum_polynomial_i64<T, const X: usize, const Y: usize>(
    l: i64,
    r: i64,
    a: i64,
    b: i64,
    m: u64,
) -> [[T; Y]; X]
where
    T: Clone + Zero + One + Add<Output = T> + Mul<Output = T>,
    AddMulOperation<T>: SemiRing<T = T, Additive: Invertible>,
{
    assert!(l <= r);
    assert!(m > 0);

    if a < 0 {
        let mut ans = floor_sum_polynomial_i64::<T, X, Y>(-r + 1, -l + 1, -a, b, m);
        for ans in ans.iter_mut().skip(1).step_by(2) {
            for ans in ans.iter_mut() {
                *ans = AddMulOperation::<T>::neg(ans);
            }
        }
        return ans;
    }

    let add_x = l;
    let n = (r - l) as u64;
    let b = a * add_x + b;

    let add_y = b.div_euclid(m as i64);
    let b = b.rem_euclid(m as i64);
    assert!(a >= 0);
    assert!(b >= 0);
    let data = floor_monoid_product::<FloorSum<AddMulOperation<T>, X, Y>>(
        FloorSum::<AddMulOperation<T>, X, Y>::to_x(),
        FloorSum::<AddMulOperation<T>, X, Y>::to_y(),
        n,
        a as u64,
        b as u64,
        m,
    );

    let offset = FloorSum::<AddMulOperation<T>, X, Y>::offset(add_x, add_y);
    FloorSum::<AddMulOperation<T>, X, Y>::operate(&offset, &data).dp
}

Trait Implementations

impl<R, const X: usize, const Y: usize> Magma for FloorSum<R, X, Y>

where R: SemiRing,

type T = FloorSumData<R, X, Y>

type of operands: $T$

fn operate(a: &Self::T, b: &Self::T) -> Self::T

binary operaion: $\circ$

fn reverse_operate(x: &Self::T, y: &Self::T) -> Self::T

fn operate_assign(x: &mut Self::T, y: &Self::T)

impl<R, const X: usize, const Y: usize> Unital for FloorSum<R, X, Y>

where R: SemiRing,

fn unit() -> Self::T

identity element: $e$

fn set_unit(x: &mut Self::T)

impl<R, const X: usize, const Y: usize> Associative for FloorSum<R, X, Y>

where R: SemiRing,