competitive::algebra

Trait SemiRing

Source 
pub trait SemiRing {
    type T: Clone;
    type Additive: AbelianMonoid<T = Self::T>;
    type Multiplicative: Monoid<T = Self::T>;

    // Provided methods
    fn zero() -> Self::T { ... }
    fn one() -> Self::T { ... }
    fn add(x: &Self::T, y: &Self::T) -> Self::T { ... }
    fn mul(x: &Self::T, y: &Self::T) -> Self::T { ... }
    fn add_assign(x: &mut Self::T, y: &Self::T) { ... }
    fn mul_assign(x: &mut Self::T, y: &Self::T) { ... }
}

Required Associated Types§

Source

type T: Clone

Source

type Additive: AbelianMonoid<T = Self::T>

Source

type Multiplicative: Monoid<T = Self::T>

Provided Methods§

Source

fn zero() -> Self::T

additive identity: $0$

Examples found in repository?
crates/competitive/src/graph/shortest_path.rs (line 93)
92    fn inf() -> Self::T {
93        PartialIgnoredOrd(M::T::maximum(), S::zero())
94    }
More examples
Hide additional examples
crates/competitive/src/math/floor_sum.rs (line 125)
124    fn to_x() -> FloorSumData<R, X, Y> {
125        let mut dp = array![array![R::zero(); Y]; X];
126        dp[0][0] = R::one();
127        FloorSumData {
128            dp,
129            dx: R::one(),
130            dy: R::zero(),
131            _marker: PhantomData,
132        }
133    }
134    fn to_y() -> FloorSumData<R, X, Y> {
135        FloorSumData {
136            dp: array![array![R::zero(); Y]; X],
137            dx: R::zero(),
138            dy: R::one(),
139            _marker: PhantomData,
140        }
141    }
142}
143
144impl<R, const X: usize, const Y: usize> FloorSum<R, X, Y>
145where
146    R: Ring,
147    R::Additive: Invertible,
148{
149    fn offset(x: i64, y: i64) -> FloorSumData<R, X, Y> {
150        FloorSumData {
151            dp: array![array![R::zero(); Y]; X],
152            dx: R::Additive::signed_pow(R::one(), x),
153            dy: R::Additive::signed_pow(R::one(), y),
154            _marker: PhantomData,
155        }
156    }
157}
158
159impl<R, const X: usize, const Y: usize> Magma for FloorSum<R, X, Y>
160where
161    R: SemiRing,
162{
163    type T = FloorSumData<R, X, Y>;
164
165    fn operate(a: &Self::T, b: &Self::T) -> Self::T {
166        let mut a = a.clone();
167        let mut b = b.clone();
168        let mut pow_x = array![R::zero(); X];
169        let mut pow_y = array![R::zero(); Y];
170        pow_x[0] = R::one();
171        pow_y[0] = R::one();
172        for i in 1..X {
173            pow_x[i] = R::mul(&pow_x[i - 1], &a.dx);
174        }
175        for j in 1..Y {
176            pow_y[j] = R::mul(&pow_y[j - 1], &a.dy);
177        }
178        macro_rules! go {
179            ($N:ident) => {
180                let mut comb = array![array![R::zero(); $N]; $N];
181                comb[0][0] = R::one();
182                let mut i = 0;
183                while i + 1 < $N {
184                    let mut j = 0;
185                    while j <= i {
186                        let x = comb[i][j].clone();
187                        R::add_assign(&mut comb[i + 1][j], &x);
188                        R::add_assign(&mut comb[i + 1][j + 1], &x);
189                        j += 1;
190                    }
191                    i += 1;
192                }
193                for i in 0..X {
194                    for j in (0..Y).rev() {
195                        for k in j + 1..Y {
196                            let mut x = b.dp[i][j].clone();
197                            R::mul_assign(&mut x, &comb[k][j]);
198                            R::mul_assign(&mut x, &pow_y[k - j]);
199                            R::add_assign(&mut b.dp[i][k], &x);
200                        }
201                    }
202                }
203                for j in 0..Y {
204                    for i in (0..X).rev() {
205                        for k in i..X {
206                            let mut x = b.dp[i][j].clone();
207                            R::mul_assign(&mut x, &comb[k][i]);
208                            R::mul_assign(&mut x, &pow_x[k - i]);
209                            R::add_assign(&mut a.dp[k][j], &x);
210                        }
211                    }
212                }
213            };
214        }
215        if X <= Y {
216            go!(Y);
217        } else {
218            go!(X);
219        }
220        R::add_assign(&mut a.dx, &b.dx);
221        R::add_assign(&mut a.dy, &b.dy);
222        a
223    }
224}
225
226impl<R, const X: usize, const Y: usize> Unital for FloorSum<R, X, Y>
227where
228    R: SemiRing,
229{
230    fn unit() -> Self::T {
231        FloorSumData {
232            dp: array![array![R::zero(); Y]; X],
233            dx: R::zero(),
234            dy: R::zero(),
235            _marker: PhantomData,
236        }
237    }
crates/competitive/src/math/subset_convolve.rs (line 23)
21    fn transform(t: Self::T, len: usize) -> Self::F {
22        let k = len.trailing_zeros() as usize;
23        let mut f = vec![vec![R::zero(); len]; k + 1];
24        for (i, t) in t.iter().enumerate() {
25            let f = &mut f[i.count_ones() as usize][i];
26            *f = R::add(f, t);
27        }
28        for f in f.iter_mut() {
29            BitwiseorConvolve::<R::Additive>::zeta_transform(f);
30        }
31        f
32    }
33
34    fn inverse_transform(mut f: Self::F, len: usize) -> Self::T {
35        for f in f.iter_mut() {
36            BitwiseorConvolve::<R::Additive>::mobius_transform(f);
37        }
38        let mut t = vec![R::zero(); len];
39        for (i, t) in t.iter_mut().enumerate() {
40            *t = R::add(t, &f[i.count_ones() as usize][i]);
41        }
42        t
43    }
Source

fn one() -> Self::T

multiplicative identity: $1$

Examples found in repository?
crates/competitive/src/graph/shortest_path.rs (line 90)
89    fn source() -> Self::T {
90        PartialIgnoredOrd(M::unit(), S::one())
91    }
More examples
Hide additional examples
crates/competitive/src/string/rolling_hash.rs (line 508)
505    fn new(base: R::T) -> Self {
506        Self {
507            base,
508            pow: vec![R::one()],
509        }
510    }
511    fn ensure_pow(&mut self, len: usize) {
512        if self.pow.len() <= len {
513            self.pow.reserve(len - self.pow.len() + 1);
514            if self.pow.is_empty() {
515                self.pow.push(R::one());
516            }
517            for _ in 0..=len - self.pow.len() {
518                self.pow.push(R::mul(self.pow.last().unwrap(), &self.base));
519            }
520        }
521    }
crates/competitive/src/math/floor_sum.rs (line 126)
124    fn to_x() -> FloorSumData<R, X, Y> {
125        let mut dp = array![array![R::zero(); Y]; X];
126        dp[0][0] = R::one();
127        FloorSumData {
128            dp,
129            dx: R::one(),
130            dy: R::zero(),
131            _marker: PhantomData,
132        }
133    }
134    fn to_y() -> FloorSumData<R, X, Y> {
135        FloorSumData {
136            dp: array![array![R::zero(); Y]; X],
137            dx: R::zero(),
138            dy: R::one(),
139            _marker: PhantomData,
140        }
141    }
142}
143
144impl<R, const X: usize, const Y: usize> FloorSum<R, X, Y>
145where
146    R: Ring,
147    R::Additive: Invertible,
148{
149    fn offset(x: i64, y: i64) -> FloorSumData<R, X, Y> {
150        FloorSumData {
151            dp: array![array![R::zero(); Y]; X],
152            dx: R::Additive::signed_pow(R::one(), x),
153            dy: R::Additive::signed_pow(R::one(), y),
154            _marker: PhantomData,
155        }
156    }
157}
158
159impl<R, const X: usize, const Y: usize> Magma for FloorSum<R, X, Y>
160where
161    R: SemiRing,
162{
163    type T = FloorSumData<R, X, Y>;
164
165    fn operate(a: &Self::T, b: &Self::T) -> Self::T {
166        let mut a = a.clone();
167        let mut b = b.clone();
168        let mut pow_x = array![R::zero(); X];
169        let mut pow_y = array![R::zero(); Y];
170        pow_x[0] = R::one();
171        pow_y[0] = R::one();
172        for i in 1..X {
173            pow_x[i] = R::mul(&pow_x[i - 1], &a.dx);
174        }
175        for j in 1..Y {
176            pow_y[j] = R::mul(&pow_y[j - 1], &a.dy);
177        }
178        macro_rules! go {
179            ($N:ident) => {
180                let mut comb = array![array![R::zero(); $N]; $N];
181                comb[0][0] = R::one();
182                let mut i = 0;
183                while i + 1 < $N {
184                    let mut j = 0;
185                    while j <= i {
186                        let x = comb[i][j].clone();
187                        R::add_assign(&mut comb[i + 1][j], &x);
188                        R::add_assign(&mut comb[i + 1][j + 1], &x);
189                        j += 1;
190                    }
191                    i += 1;
192                }
193                for i in 0..X {
194                    for j in (0..Y).rev() {
195                        for k in j + 1..Y {
196                            let mut x = b.dp[i][j].clone();
197                            R::mul_assign(&mut x, &comb[k][j]);
198                            R::mul_assign(&mut x, &pow_y[k - j]);
199                            R::add_assign(&mut b.dp[i][k], &x);
200                        }
201                    }
202                }
203                for j in 0..Y {
204                    for i in (0..X).rev() {
205                        for k in i..X {
206                            let mut x = b.dp[i][j].clone();
207                            R::mul_assign(&mut x, &comb[k][i]);
208                            R::mul_assign(&mut x, &pow_x[k - i]);
209                            R::add_assign(&mut a.dp[k][j], &x);
210                        }
211                    }
212                }
213            };
214        }
215        if X <= Y {
216            go!(Y);
217        } else {
218            go!(X);
219        }
220        R::add_assign(&mut a.dx, &b.dx);
221        R::add_assign(&mut a.dy, &b.dy);
222        a
223    }
Source

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

additive operaion: $+$

Examples found in repository?
crates/competitive/src/string/rolling_hash.rs (line 523)
522    fn mul1_add(&self, x: &R::T, y: &R::T) -> R::T {
523        R::add(&R::mul(x, &self.base), y)
524    }
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    }
More examples
Hide additional examples
crates/competitive/src/graph/shortest_path.rs (line 101)
98    fn add_assign(x: &mut Self::T, y: &Self::T) -> bool {
99        match x.0.cmp(&y.0) {
100            Ordering::Equal => {
101                x.1 = S::add(&x.1, &y.1);
102                false
103            }
104            Ordering::Greater => {
105                *x = y.clone();
106                true
107            }
108            _ => false,
109        }
110    }
crates/competitive/src/math/subset_convolve.rs (line 26)
21    fn transform(t: Self::T, len: usize) -> Self::F {
22        let k = len.trailing_zeros() as usize;
23        let mut f = vec![vec![R::zero(); len]; k + 1];
24        for (i, t) in t.iter().enumerate() {
25            let f = &mut f[i.count_ones() as usize][i];
26            *f = R::add(f, t);
27        }
28        for f in f.iter_mut() {
29            BitwiseorConvolve::<R::Additive>::zeta_transform(f);
30        }
31        f
32    }
33
34    fn inverse_transform(mut f: Self::F, len: usize) -> Self::T {
35        for f in f.iter_mut() {
36            BitwiseorConvolve::<R::Additive>::mobius_transform(f);
37        }
38        let mut t = vec![R::zero(); len];
39        for (i, t) in t.iter_mut().enumerate() {
40            *t = R::add(t, &f[i.count_ones() as usize][i]);
41        }
42        t
43    }
44
45    fn multiply(f: &mut Self::F, g: &Self::F) {
46        for i in (0..f.len()).rev() {
47            let (lf, rf) = f.split_at_mut(i);
48            for (x, y) in rf[0].iter_mut().zip(&g[0]) {
49                *x = R::mul(x, y);
50            }
51            for (x, y) in lf.iter().rev().zip(g.iter().skip(1)) {
52                for ((x, y), z) in x.iter().zip(y).zip(&mut rf[0]) {
53                    *z = R::add(z, &R::mul(x, y));
54                }
55            }
56        }
57    }
crates/competitive/src/math/quotient_array.rs (line 100)
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 mul(x: &Self::T, y: &Self::T) -> Self::T

multiplicative operaion: $+$

Examples found in repository?
crates/competitive/src/graph/shortest_path.rs (line 96)
95    fn mul(x: &Self::T, y: &Self::T) -> Self::T {
96        PartialIgnoredOrd(M::operate(&x.0, &y.0), S::mul(&x.1, &y.1))
97    }
More examples
Hide additional examples
crates/competitive/src/math/bitwiseand_convolve.rs (line 53)
51    fn multiply(f: &mut Self::F, g: &Self::F) {
52        for (f, g) in f.iter_mut().zip(g) {
53            *f = R::mul(f, g);
54        }
55    }
56
57    fn convolve(a: Self::T, b: Self::T) -> Self::T {
58        assert_eq!(a.len(), b.len());
59        let len = a.len();
60        let same = a == b;
61        let mut a = Self::transform(a, len);
62        if same {
63            for a in a.iter_mut() {
64                *a = R::mul(a, a);
65            }
66        } else {
67            let b = Self::transform(b, len);
68            Self::multiply(&mut a, &b);
69        }
70        Self::inverse_transform(a, len)
71    }
crates/competitive/src/math/bitwiseor_convolve.rs (line 53)
51    fn multiply(f: &mut Self::F, g: &Self::F) {
52        for (f, g) in f.iter_mut().zip(g) {
53            *f = R::mul(f, g);
54        }
55    }
56
57    fn convolve(a: Self::T, b: Self::T) -> Self::T {
58        assert_eq!(a.len(), b.len());
59        let len = a.len();
60        let same = a == b;
61        let mut a = Self::transform(a, len);
62        if same {
63            for a in a.iter_mut() {
64                *a = R::mul(a, a);
65            }
66        } else {
67            let b = Self::transform(b, len);
68            Self::multiply(&mut a, &b);
69        }
70        Self::inverse_transform(a, len)
71    }
crates/competitive/src/math/bitwisexor_convolve.rs (line 52)
50    fn multiply(f: &mut Self::F, g: &Self::F) {
51        for (f, g) in f.iter_mut().zip(g) {
52            *f = R::mul(f, g);
53        }
54    }
55
56    fn convolve(a: Self::T, b: Self::T) -> Self::T {
57        assert_eq!(a.len(), b.len());
58        let len = a.len();
59        let same = a == b;
60        let mut a = Self::transform(a, len);
61        if same {
62            for a in a.iter_mut() {
63                *a = R::mul(a, a);
64            }
65        } else {
66            let b = Self::transform(b, len);
67            Self::multiply(&mut a, &b);
68        }
69        Self::inverse_transform(a, len)
70    }
71}
72
73impl<R> ConvolveSteps for BitwisexorConvolve<R, true>
74where
75    R: Field,
76    R::T: PartialEq,
77    R::Additive: Invertible,
78    R::Multiplicative: Invertible,
79    R::T: TryFrom<usize>,
80    <R::T as TryFrom<usize>>::Error: Debug,
81{
82    type T = Vec<R::T>;
83    type F = Vec<R::T>;
84
85    fn length(t: &Self::T) -> usize {
86        t.len()
87    }
88
89    fn transform(mut t: Self::T, _len: usize) -> Self::F {
90        BitwisexorConvolve::<R::Additive, true>::hadamard_transform(&mut t);
91        t
92    }
93
94    fn inverse_transform(mut f: Self::F, len: usize) -> Self::T {
95        BitwisexorConvolve::<R::Additive, true>::hadamard_transform(&mut f);
96        let len = R::T::try_from(len).unwrap();
97        for f in f.iter_mut() {
98            *f = R::div(f, &len);
99        }
100        f
101    }
102
103    fn multiply(f: &mut Self::F, g: &Self::F) {
104        for (f, g) in f.iter_mut().zip(g) {
105            *f = R::mul(f, g);
106        }
107    }
108
109    fn convolve(a: Self::T, b: Self::T) -> Self::T {
110        assert_eq!(a.len(), b.len());
111        let len = a.len();
112        let same = a == b;
113        let mut a = Self::transform(a, len);
114        if same {
115            for a in a.iter_mut() {
116                *a = R::mul(a, a);
117            }
118        } else {
119            let b = Self::transform(b, len);
120            Self::multiply(&mut a, &b);
121        }
122        Self::inverse_transform(a, len)
123    }
crates/competitive/src/math/gcd_convolve.rs (line 66)
64    fn multiply(f: &mut Self::F, g: &Self::F) {
65        for (f, g) in f.iter_mut().zip(g) {
66            *f = R::mul(f, g);
67        }
68    }
crates/competitive/src/math/lcm_convolve.rs (line 66)
64    fn multiply(f: &mut Self::F, g: &Self::F) {
65        for (f, g) in f.iter_mut().zip(g) {
66            *f = R::mul(f, g);
67        }
68    }
Additional examples can be found in:
Source

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

Examples found in repository?
crates/competitive/src/math/floor_sum.rs (line 220)
165    fn operate(a: &Self::T, b: &Self::T) -> Self::T {
166        let mut a = a.clone();
167        let mut b = b.clone();
168        let mut pow_x = array![R::zero(); X];
169        let mut pow_y = array![R::zero(); Y];
170        pow_x[0] = R::one();
171        pow_y[0] = R::one();
172        for i in 1..X {
173            pow_x[i] = R::mul(&pow_x[i - 1], &a.dx);
174        }
175        for j in 1..Y {
176            pow_y[j] = R::mul(&pow_y[j - 1], &a.dy);
177        }
178        macro_rules! go {
179            ($N:ident) => {
180                let mut comb = array![array![R::zero(); $N]; $N];
181                comb[0][0] = R::one();
182                let mut i = 0;
183                while i + 1 < $N {
184                    let mut j = 0;
185                    while j <= i {
186                        let x = comb[i][j].clone();
187                        R::add_assign(&mut comb[i + 1][j], &x);
188                        R::add_assign(&mut comb[i + 1][j + 1], &x);
189                        j += 1;
190                    }
191                    i += 1;
192                }
193                for i in 0..X {
194                    for j in (0..Y).rev() {
195                        for k in j + 1..Y {
196                            let mut x = b.dp[i][j].clone();
197                            R::mul_assign(&mut x, &comb[k][j]);
198                            R::mul_assign(&mut x, &pow_y[k - j]);
199                            R::add_assign(&mut b.dp[i][k], &x);
200                        }
201                    }
202                }
203                for j in 0..Y {
204                    for i in (0..X).rev() {
205                        for k in i..X {
206                            let mut x = b.dp[i][j].clone();
207                            R::mul_assign(&mut x, &comb[k][i]);
208                            R::mul_assign(&mut x, &pow_x[k - i]);
209                            R::add_assign(&mut a.dp[k][j], &x);
210                        }
211                    }
212                }
213            };
214        }
215        if X <= Y {
216            go!(Y);
217        } else {
218            go!(X);
219        }
220        R::add_assign(&mut a.dx, &b.dx);
221        R::add_assign(&mut a.dy, &b.dy);
222        a
223    }
Source

fn mul_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§