Invertible

competitive::algebra

Trait Invertible 

Source 
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§

Source

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

$a$ where $a \circ x = e$

Provided Methods§

Source

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

Examples found in repository?
crates/competitive/src/algebra/magma.rs (line 186)
185    fn rinv_operate_assign(x: &mut Self::T, y: &Self::T) {
186        *x = Self::rinv_operate(x, y);
187    }
More examples
Hide additional 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/math/bitwisexor_convolve.rs (line 15)
12    pub fn hadamard_transform(f: &mut [G::T]) {
13        bitwise_transform(f, |x, y| {
14            let t = G::operate(x, y);
15            *y = G::rinv_operate(x, y);
16            *x = t;
17        });
18    }
crates/competitive/src/math/gcd_convolve.rs (line 35)
30    pub fn mobius_transform(f: &mut [G::T]) {
31        let n = f.len().saturating_sub(1) as u64;
32        with_prime_list(n, |pl| {
33            for &p in pl.primes_lte(n).iter() {
34                for (i, j) in (0..f.len()).step_by(p as _).enumerate() {
35                    f[i] = G::rinv_operate(&f[i], &f[j]);
36                }
37            }
38        })
39    }
Additional examples can be found in:
Source

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
Hide additional 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.

Implementations on Foreign Types§

Source§

impl Invertible for ()

Source§

fn inverse(_x: &Self::T) -> Self::T

Source§

impl<A: Invertible> Invertible for (A,)

Source§

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

Source§

impl<A: Invertible, B: Invertible> Invertible for (A, B)

Source§

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

Source§

impl<A: Invertible, B: Invertible, C: Invertible> Invertible for (A, B, C)

Source§

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

Source§

impl<A: Invertible, B: Invertible, C: Invertible, D: Invertible> Invertible for (A, B, C, D)

Source§

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

Source§

impl<A: Invertible, B: Invertible, C: Invertible, D: Invertible, E: Invertible> Invertible for (A, B, C, D, E)

Source§

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

Source§

impl<A: Invertible, B: Invertible, C: Invertible, D: Invertible, E: Invertible, F: Invertible> Invertible for (A, B, C, D, E, F)

Source§

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

Source§

impl<A: Invertible, B: Invertible, C: Invertible, D: Invertible, E: Invertible, F: Invertible, G: Invertible> Invertible for (A, B, C, D, E, F, G)

Source§

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

Source§

impl<A: Invertible, B: Invertible, C: Invertible, D: Invertible, E: Invertible, F: Invertible, G: Invertible, H: Invertible> Invertible for (A, B, C, D, E, F, G, H)

Source§

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

Source§

impl<A: Invertible, B: Invertible, C: Invertible, D: Invertible, E: Invertible, F: Invertible, G: Invertible, H: Invertible, I: Invertible> Invertible for (A, B, C, D, E, F, G, H, I)

Source§

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

Source§

impl<A: Invertible, B: Invertible, C: Invertible, D: Invertible, E: Invertible, F: Invertible, G: Invertible, H: Invertible, I: Invertible, J: Invertible> Invertible for (A, B, C, D, E, F, G, H, I, J)

Source§

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

Implementors§

Source§

impl Invertible for PermutationOperation

Source§

impl Invertible for Mersenne61Add

Source§

impl<M> Invertible for ReverseOperation<M>
where M: Invertible,

Source§

impl<M, const N: usize> Invertible for ArrayOperation<M, N>
where M: Invertible,

Source§

impl<T> Invertible for AdditiveOperation<T>
where T: Clone + Zero + Add<Output = T> + Sub<Output = T> + Neg<Output = T>,

Source§

impl<T> Invertible for BitXorOperation<T>
where T: Clone + BitXorIdentity,

Source§

impl<T> Invertible for LinearOperation<T>
where T: Clone + Zero + One + Add<Output = T> + Sub<Output = T> + Neg<Output = T> + Mul<Output = T> + Div<Output = T>,

Source§

impl<T> Invertible for MultiplicativeOperation<T>
where T: Clone + One + Mul<Output = T> + Div<Output = T>,