competitive::algebra

Trait Ring

Source 
pub trait Ring: SemiRing
where
    Self::Additive: Invertible,
{
    // Provided methods
    fn neg(x: &Self::T) -> Self::T { ... }
    fn sub(x: &Self::T, y: &Self::T) -> Self::T { ... }
    fn sub_assign(x: &mut Self::T, y: &Self::T) { ... }
}

Provided Methods§

Source

fn neg(x: &Self::T) -> Self::T

additive inverse: $-$

Examples found in repository?
crates/competitive/src/math/floor_sum.rs (line 319)
301pub fn floor_sum_polynomial_i64<T, const X: usize, const Y: usize>(
302    l: i64,
303    r: i64,
304    a: i64,
305    b: i64,
306    m: u64,
307) -> [[T; Y]; X]
308where
309    T: Clone + Zero + One + Add<Output = T> + Mul<Output = T>,
310    <AddMulOperation<T> as SemiRing>::Additive: Invertible,
311{
312    assert!(l <= r);
313    assert!(m > 0);
314
315    if a < 0 {
316        let mut ans = floor_sum_polynomial_i64::<T, X, Y>(-r + 1, -l + 1, -a, b, m);
317        for i in (1..X).step_by(2) {
318            for j in 0..Y {
319                ans[i][j] = AddMulOperation::<T>::neg(&ans[i][j]);
320            }
321        }
322        return ans;
323    }
324
325    let add_x = l;
326    let n = (r - l) as u64;
327    let b = a * add_x + b;
328
329    let add_y = b.div_euclid(m as i64);
330    let b = b.rem_euclid(m as i64);
331    assert!(a >= 0);
332    assert!(b >= 0);
333    let data = floor_monoid_product::<FloorSum<AddMulOperation<T>, X, Y>>(
334        FloorSum::<AddMulOperation<T>, X, Y>::to_x(),
335        FloorSum::<AddMulOperation<T>, X, Y>::to_y(),
336        n,
337        a as u64,
338        b as u64,
339        m,
340    );
341
342    let offset = FloorSum::<AddMulOperation<T>, X, Y>::offset(add_x, add_y);
343    FloorSum::<AddMulOperation<T>, X, Y>::operate(&offset, &data).dp
344}
Source

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

additive right inversed operaion: $-$

Examples found in repository?
crates/competitive/src/string/rolling_hash.rs (line 535)
533    fn muln_sub(&mut self, l: &R::T, r: &R::T, n: usize) -> R::T {
534        if let Some(pow) = self.pow.get(n) {
535            R::sub(r, &R::mul(l, pow))
536        } else {
537            let pow = <R::Multiplicative as Monoid>::pow(self.base.clone(), n);
538            R::sub(r, &R::mul(l, &pow))
539        }
540    }
More examples
Hide additional examples
crates/competitive/src/math/quotient_array.rs (line 99)
82    pub fn min_25_sieve<R>(&self, mut f: impl FnMut(u64, u32) -> T) -> Self
83    where
84        T: Clone + One,
85        R: Ring<T = T>,
86        R::Additive: Invertible,
87    {
88        let mut dp = self.clone();
89        with_prime_list(self.isqrtn, |pl| {
90            for &p in pl.primes_lte(self.isqrtn).iter().rev() {
91                let k = self.quotient_index(p);
92                for (i, q) in Self::index_iter(self.n, self.isqrtn).enumerate() {
93                    let mut pc = p;
94                    if pc * p > q {
95                        break;
96                    }
97                    let mut c = 1;
98                    while q / p >= pc {
99                        let x = R::mul(&f(p, c), &(R::sub(&dp[q / pc], &self.data[k])));
100                        let x = R::add(&x, &f(p, c + 1));
101                        dp.data[i] = R::add(&dp.data[i], &x);
102                        c += 1;
103                        pc *= p;
104                    }
105                }
106            }
107        });
108        for x in &mut dp.data {
109            *x = R::add(x, &T::one());
110        }
111        dp
112    }
Source

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

Dyn Compatibility§

This trait is not dyn compatible.

In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.

Implementors§

Source§

impl<R> Ring for R
where R: SemiRing, R::Additive: Invertible,