competitive::algebra

Trait Monoid

Source 
pub trait Monoid: SemiGroup + Unital {
    // Provided methods
    fn pow<E>(x: Self::T, exp: E) -> Self::T
       where E: ExpBits { ... }
    fn fold<I>(iter: I) -> Self::T
       where I: IntoIterator<Item = Self::T> { ... }
}
Expand description

associative binary operation and an identity element

Provided Methods§

Source

fn pow<E>(x: Self::T, exp: E) -> Self::T
where E: ExpBits,

binary exponentiation: $x^n = x\circ\ddots\circ x$

Examples found in repository?
crates/competitive/src/algebra/magma.rs (line 158)
153    fn signed_pow<E>(x: Self::T, exp: E) -> Self::T
154    where
155        E: SignedExpBits,
156    {
157        let (neg, exp) = E::neg_and_bits(exp);
158        let res = Self::pow(x, exp);
159        if neg { Self::inverse(&res) } else { res }
160    }
More examples
Hide additional examples
crates/competitive/src/string/rolling_hash.rs (line 529)
525    fn muln_add(&mut self, x: &R::T, y: &R::T, n: usize) -> R::T {
526        if let Some(pow) = self.pow.get(n) {
527            R::add(&R::mul(x, pow), y)
528        } else {
529            let pow = <R::Multiplicative as Monoid>::pow(self.base.clone(), n);
530            R::add(&R::mul(x, &pow), y)
531        }
532    }
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    }
crates/competitive/src/math/floor_sum.rs (line 260)
242fn floor_monoid_product<M>(
243    mut x: M::T,
244    mut y: M::T,
245    mut n: u64,
246    mut a: u64,
247    mut b: u64,
248    mut m: u64,
249) -> M::T
250where
251    M: Monoid,
252{
253    let mut c = (a * n + b) / m;
254    let mut pre = M::unit();
255    let mut suf = M::unit();
256    loop {
257        let (p, q) = (a / m, b / m);
258        a %= m;
259        b %= m;
260        x = M::operate(&x, &M::pow(y.clone(), p));
261        pre = M::operate(&pre, &M::pow(y.clone(), q));
262        c -= p * n + q;
263        if c == 0 {
264            break;
265        }
266        let d = (m * c - b - 1) / a + 1;
267        suf = M::operate(&y, &M::operate(&M::pow(x.clone(), n - d), &suf));
268        b = m - b - 1 + a;
269        n = c - 1;
270        c = d;
271        swap(&mut m, &mut a);
272        swap(&mut x, &mut y);
273    }
274    x = M::pow(x.clone(), n);
275    M::operate(&M::operate(&pre, &x), &suf)
276}
crates/competitive/src/algorithm/baby_step_giant_step.rs (line 21)
6pub fn baby_step_giant_step<M>(x: M::T, y: M::T, n: usize) -> Option<usize>
7where
8    M: Monoid,
9    M::T: Eq + Hash,
10{
11    if M::is_unit(&y) {
12        return Some(0);
13    }
14    let block_size = 1usize.max((n as f64).sqrt() as _);
15    let mut baby = HashSet::new();
16    let mut t = y.clone();
17    for _ in 0..block_size {
18        t = M::operate(&x, &t);
19        baby.insert(t.clone());
20    }
21    let g = M::pow(x.clone(), block_size);
22    let mut t = M::unit();
23    let mut fail = 0usize;
24    for k in (0..n).step_by(block_size) {
25        let nt = M::operate(&g, &t);
26        if baby.contains(&nt) {
27            for m in k..n.min(k + block_size) {
28                if t == y {
29                    return Some(m);
30                }
31                t = M::operate(&x, &t);
32            }
33            fail += 1;
34            if fail >= 2 {
35                break;
36            }
37        }
38        t = nt;
39    }
40    None
41}
Source

fn fold<I>(iter: I) -> Self::T
where I: IntoIterator<Item = 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<M> Monoid for M
where M: SemiGroup + Unital,