pub trait Invertible: Magma + Unital {
// Required method
fn inverse(x: &Self::T) -> Self::T;
// Provided methods
fn rinv_operate(x: &Self::T, y: &Self::T) -> Self::T { ... }
fn rinv_operate_assign(x: &mut Self::T, y: &Self::T) { ... }
}Expand description
$\exists e \in T, \forall a \in T, \exists b,c \in T, b \circ a = a \circ c = e$
Required Methods§
Provided Methods§
Sourcefn rinv_operate(x: &Self::T, y: &Self::T) -> Self::T
fn rinv_operate(x: &Self::T, y: &Self::T) -> Self::T
Examples found in repository?
More examples
crates/competitive/src/algebra/ring.rs (line 58)
57 fn sub(x: &Self::T, y: &Self::T) -> Self::T {
58 <Self::Additive as Invertible>::rinv_operate(x, y)
59 }
60
61 fn sub_assign(x: &mut Self::T, y: &Self::T) {
62 <Self::Additive as Invertible>::rinv_operate_assign(x, y);
63 }
64}
65
66impl<R> Ring for R where R: SemiRing<Additive: Invertible> {}
67
68pub trait Field: Ring<Multiplicative: Invertible> {
69 /// multiplicative inverse: $-$
70 fn inv(x: &Self::T) -> Self::T {
71 <Self::Multiplicative as Invertible>::inverse(x)
72 }
73 /// multiplicative right inversed operaion: $-$
74 fn div(x: &Self::T, y: &Self::T) -> Self::T {
75 <Self::Multiplicative as Invertible>::rinv_operate(x, y)
76 }crates/competitive/src/math/bitwiseand_convolve.rs (line 24)
23 pub fn mobius_transform(f: &mut [G::T]) {
24 bitwise_transform(f, |x, y| *x = G::rinv_operate(x, y));
25 }
26}
27
28impl<R> ConvolveSteps for BitwiseandConvolve<R>
29where
30 R: Ring<T: PartialEq, Additive: Invertible>,
31{
32 type T = Vec<R::T>;
33 type F = Vec<R::T>;
34
35 fn length(t: &Self::T) -> usize {
36 t.len()
37 }
38
39 fn transform(mut t: Self::T, _len: usize) -> Self::F {
40 BitwiseandConvolve::<R::Additive>::zeta_transform(&mut t);
41 t
42 }
43
44 fn inverse_transform(mut f: Self::F, _len: usize) -> Self::T {
45 BitwiseandConvolve::<R::Additive>::mobius_transform(&mut f);
46 f
47 }
48
49 fn multiply(f: &mut Self::F, g: &Self::F) {
50 for (f, g) in f.iter_mut().zip(g) {
51 *f = R::mul(f, g);
52 }
53 }
54
55 fn convolve(a: Self::T, b: Self::T) -> Self::T {
56 assert_eq!(a.len(), b.len());
57 let len = a.len();
58 let same = a == b;
59 let mut a = Self::transform(a, len);
60 if same {
61 for a in a.iter_mut() {
62 *a = R::mul(a, a);
63 }
64 } else {
65 let b = Self::transform(b, len);
66 Self::multiply(&mut a, &b);
67 }
68 Self::inverse_transform(a, len)
69 }
70}
71
72pub struct OnlineSupersetZetaTransform<M>
73where
74 M: Monoid,
75{
76 data: Vec<M::T>,
77}
78
79impl<M> OnlineSupersetZetaTransform<M>
80where
81 M: Monoid,
82{
83 pub fn new(size: usize) -> Self {
84 Self {
85 data: Vec::with_capacity(size),
86 }
87 }
88
89 pub fn push(&mut self, x: M::T) {
90 let i = self.data.len();
91 self.data.push(x);
92 let mut k = 0;
93 while i >> k & 1 == 1 {
94 let size = 1 << k;
95 let chunk = &mut self.data[i - (size * 2 - 1)..];
96 let (x, y) = chunk.split_at_mut(size);
97 for (x, y) in x.iter_mut().zip(y.iter()) {
98 M::operate_assign(x, y);
99 }
100 k += 1;
101 }
102 }
103
104 pub fn get(&self, index: usize) -> M::T {
105 let mut cur = self.data.len();
106 let mut s = M::unit();
107 while cur != 0 {
108 let d = cur.trailing_zeros() as usize;
109 let base = cur ^ (1 << d);
110 if (!base & index) >> d == 0 {
111 let mask = (1 << d) - 1;
112 s = M::operate(&s, &self.data[base ^ ((index ^ base) & mask)]);
113 }
114 cur = base;
115 }
116 s
117 }
118}
119
120pub struct OnlineSupersetMobiusTransform<M>
121where
122 M: Group,
123{
124 data: Vec<M::T>,
125}
126
127impl<M> OnlineSupersetMobiusTransform<M>
128where
129 M: Group,
130{
131 pub fn new(size: usize) -> Self {
132 Self {
133 data: Vec::with_capacity(size),
134 }
135 }
136
137 pub fn push(&mut self, x: M::T) {
138 let i = self.data.len();
139 self.data.push(x);
140 let mut k = 0;
141 while i >> k & 1 == 1 {
142 let size = 1 << k;
143 let chunk = &mut self.data[i - (size * 2 - 1)..];
144 let (x, y) = chunk.split_at_mut(size);
145 for (x, y) in x.iter_mut().zip(y.iter()) {
146 M::rinv_operate_assign(x, y);
147 }
148 k += 1;
149 }
150 }
151
152 pub fn get(&self, index: usize) -> M::T {
153 let mut cur = self.data.len();
154 let mut s = M::unit();
155 while cur != 0 {
156 let d = cur.trailing_zeros() as usize;
157 let base = cur ^ (1 << d);
158 if (!base & index) >> d == 0 {
159 let mask = (1 << d) - 1;
160 let j = base ^ ((index ^ base) & mask);
161 if ((index ^ base) >> d).count_ones() & 1 == 1 {
162 s = M::rinv_operate(&s, &self.data[j]);
163 } else {
164 s = M::operate(&s, &self.data[j]);
165 }
166 }
167 cur = base;
168 }
169 s
170 }crates/competitive/src/math/bitwiseor_convolve.rs (line 24)
23 pub fn mobius_transform(f: &mut [G::T]) {
24 bitwise_transform(f, |y, x| *x = G::rinv_operate(x, y));
25 }
26}
27
28impl<R> ConvolveSteps for BitwiseorConvolve<R>
29where
30 R: Ring<T: PartialEq, Additive: Invertible>,
31{
32 type T = Vec<R::T>;
33 type F = Vec<R::T>;
34
35 fn length(t: &Self::T) -> usize {
36 t.len()
37 }
38
39 fn transform(mut t: Self::T, _len: usize) -> Self::F {
40 BitwiseorConvolve::<R::Additive>::zeta_transform(&mut t);
41 t
42 }
43
44 fn inverse_transform(mut f: Self::F, _len: usize) -> Self::T {
45 BitwiseorConvolve::<R::Additive>::mobius_transform(&mut f);
46 f
47 }
48
49 fn multiply(f: &mut Self::F, g: &Self::F) {
50 for (f, g) in f.iter_mut().zip(g) {
51 *f = R::mul(f, g);
52 }
53 }
54
55 fn convolve(a: Self::T, b: Self::T) -> Self::T {
56 assert_eq!(a.len(), b.len());
57 let len = a.len();
58 let same = a == b;
59 let mut a = Self::transform(a, len);
60 if same {
61 for a in a.iter_mut() {
62 *a = R::mul(a, a);
63 }
64 } else {
65 let b = Self::transform(b, len);
66 Self::multiply(&mut a, &b);
67 }
68 Self::inverse_transform(a, len)
69 }
70}
71
72pub struct OnlineSubsetZetaTransform<M>
73where
74 M: Monoid,
75{
76 data: Vec<M::T>,
77}
78
79impl<M> OnlineSubsetZetaTransform<M>
80where
81 M: Monoid,
82{
83 pub fn new(size: usize) -> Self {
84 Self {
85 data: Vec::with_capacity(size),
86 }
87 }
88
89 pub fn push(&mut self, x: M::T) {
90 let i = self.data.len();
91 self.data.push(x);
92 let mut k = 0;
93 while i >> k & 1 == 1 {
94 let size = 1 << k;
95 let chunk = &mut self.data[i - (size * 2 - 1)..];
96 let (x, y) = chunk.split_at_mut(size);
97 for (x, y) in x.iter().zip(y.iter_mut()) {
98 *y = M::operate(x, y);
99 }
100 k += 1;
101 }
102 }
103
104 pub fn get(&self, index: usize) -> M::T {
105 let mut cur = self.data.len();
106 let mut s = M::unit();
107 while cur != 0 {
108 let d = cur.trailing_zeros() as usize;
109 let base = cur ^ (1 << d);
110 if (base & !index) >> d == 0 {
111 let mask = (1 << d) - 1;
112 s = M::operate(&s, &self.data[base ^ ((index ^ base) & mask)]);
113 }
114 cur = base;
115 }
116 s
117 }
118}
119
120pub struct OnlineSubsetMobiusTransform<M>
121where
122 M: Group,
123{
124 data: Vec<M::T>,
125}
126
127impl<M> OnlineSubsetMobiusTransform<M>
128where
129 M: Group,
130{
131 pub fn new(size: usize) -> Self {
132 Self {
133 data: Vec::with_capacity(size),
134 }
135 }
136
137 pub fn push(&mut self, x: M::T) {
138 let i = self.data.len();
139 self.data.push(x);
140 let mut k = 0;
141 while i >> k & 1 == 1 {
142 let size = 1 << k;
143 let chunk = &mut self.data[i - (size * 2 - 1)..];
144 let (x, y) = chunk.split_at_mut(size);
145 for (x, y) in x.iter().zip(y.iter_mut()) {
146 *y = M::rinv_operate(y, x);
147 }
148 k += 1;
149 }
150 }
151
152 pub fn get(&self, index: usize) -> M::T {
153 let mut cur = self.data.len();
154 let mut s = M::unit();
155 while cur != 0 {
156 let d = cur.trailing_zeros() as usize;
157 let base = cur ^ (1 << d);
158 if (base & !index) >> d == 0 {
159 let mask = (1 << d) - 1;
160 let j = base ^ ((index ^ base) & mask);
161 if ((index ^ base) >> d).count_ones() & 1 == 1 {
162 s = M::rinv_operate(&s, &self.data[j]);
163 } else {
164 s = M::operate(&s, &self.data[j]);
165 }
166 }
167 cur = base;
168 }
169 s
170 }crates/competitive/src/data_structure/wavelet_matrix.rs (lines 338-341)
335 fn range_sum(&self, level: usize, range: Range<usize>) -> M::T {
336 let offset = level * (self.wavelet_matrix.len + 1);
337 unsafe {
338 M::rinv_operate(
339 self.prefix.get_unchecked(offset + range.end),
340 self.prefix.get_unchecked(offset + range.start),
341 )
342 }
343 }
344
345 pub fn fold_lessthan(&self, val: T, range: Range<usize>) -> M::T {
346 self.fold_lessthan_with_count(val, range).1
347 }
348
349 pub fn fold_lessthan_with_count(&self, val: T, mut range: Range<usize>) -> (usize, M::T) {
350 debug_assert!(range.end <= self.wavelet_matrix.len);
351 let idx = self.wavelet_matrix.compress.index_lower_bound(&val);
352 let mut count = 0;
353 let mut sum = M::unit();
354 for d in (0..self.wavelet_matrix.bit_length).rev() {
355 let level = self.wavelet_matrix.level(d);
356 let start0 = self.wavelet_matrix.rank0(level, range.start);
357 let end0 = self.wavelet_matrix.rank0(level, range.end);
358 if ((idx >> d) & 1) != 0 {
359 count += end0 - start0;
360 sum = M::operate(&sum, &self.range_sum(level + 1, start0..end0));
361 range.start = self.wavelet_matrix.zeros[level] + (range.start - start0);
362 range.end = self.wavelet_matrix.zeros[level] + (range.end - end0);
363 } else {
364 range.start = start0;
365 range.end = end0;
366 }
367 }
368 (count, sum)
369 }
370
371 pub fn fold_range(&self, valrange: Range<T>, range: Range<usize>) -> M::T {
372 M::rinv_operate(
373 &self.fold_lessthan(valrange.end, range.clone()),
374 &self.fold_lessthan(valrange.start, range),
375 )
376 }
377
378 pub fn fold_range_with_count(&self, valrange: Range<T>, range: Range<usize>) -> (usize, M::T) {
379 let (count_upper, sum_upper) = self.fold_lessthan_with_count(valrange.end, range.clone());
380 let (count_lower, sum_lower) = self.fold_lessthan_with_count(valrange.start, range);
381 (
382 count_upper - count_lower,
383 M::rinv_operate(&sum_upper, &sum_lower),
384 )
385 }Additional examples can be found in:
- crates/competitive/src/math/gcd_convolve.rs
- crates/competitive/src/math/lcm_convolve.rs
- crates/competitive/src/data_structure/binary_indexed_tree_2d.rs
- crates/competitive/src/math/quotient_array.rs
- crates/competitive/src/data_structure/accumulate.rs
- crates/competitive/src/data_structure/union_find.rs
- crates/competitive/src/data_structure/submask_range_query.rs
Sourcefn rinv_operate_assign(x: &mut Self::T, y: &Self::T)
fn rinv_operate_assign(x: &mut Self::T, y: &Self::T)
Examples found in repository?
crates/competitive/src/algebra/ring.rs (line 62)
61 fn sub_assign(x: &mut Self::T, y: &Self::T) {
62 <Self::Additive as Invertible>::rinv_operate_assign(x, y);
63 }
64}
65
66impl<R> Ring for R where R: SemiRing<Additive: Invertible> {}
67
68pub trait Field: Ring<Multiplicative: Invertible> {
69 /// multiplicative inverse: $-$
70 fn inv(x: &Self::T) -> Self::T {
71 <Self::Multiplicative as Invertible>::inverse(x)
72 }
73 /// multiplicative right inversed operaion: $-$
74 fn div(x: &Self::T, y: &Self::T) -> Self::T {
75 <Self::Multiplicative as Invertible>::rinv_operate(x, y)
76 }
77
78 fn div_assign(x: &mut Self::T, y: &Self::T) {
79 <Self::Multiplicative as Invertible>::rinv_operate_assign(x, y);
80 }More examples
crates/competitive/src/math/bitwiseand_convolve.rs (line 146)
137 pub fn push(&mut self, x: M::T) {
138 let i = self.data.len();
139 self.data.push(x);
140 let mut k = 0;
141 while i >> k & 1 == 1 {
142 let size = 1 << k;
143 let chunk = &mut self.data[i - (size * 2 - 1)..];
144 let (x, y) = chunk.split_at_mut(size);
145 for (x, y) in x.iter_mut().zip(y.iter()) {
146 M::rinv_operate_assign(x, y);
147 }
148 k += 1;
149 }
150 }crates/competitive/src/math/quotient_array.rs (line 74)
61 pub fn lucy_dp<G>(mut self, mut mul_p: impl FnMut(T, u64) -> T) -> Self
62 where
63 G: Group<T = T>,
64 {
65 with_prime_list(self.isqrtn, |pl| {
66 for &p in pl.primes_lte(self.isqrtn) {
67 let k = self.quotient_index(p - 1);
68 let p2 = p * p;
69 for (i, q) in Self::index_iter(self.n, self.isqrtn).enumerate() {
70 if q < p2 {
71 break;
72 }
73 let diff = mul_p(G::rinv_operate(&self[q / p], &self.data[k]), p);
74 G::rinv_operate_assign(&mut self.data[i], &diff);
75 }
76 }
77 });
78 self
79 }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.