competitive/algebra/
ring.rs

1use super::*;
2use std::{
3    marker::PhantomData,
4    ops::{Add, Mul},
5};
6
7pub trait SemiRing {
8    type T: Clone;
9    type Additive: AbelianMonoid<T = Self::T>;
10    type Multiplicative: Monoid<T = Self::T>;
11    /// additive identity: $0$
12    fn zero() -> Self::T {
13        <Self::Additive as Unital>::unit()
14    }
15    /// checks if the element is zero
16    fn is_zero(x: &Self::T) -> bool
17    where
18        Self::T: PartialEq,
19    {
20        *x == Self::zero()
21    }
22    /// multiplicative identity: $1$
23    fn one() -> Self::T {
24        <Self::Multiplicative as Unital>::unit()
25    }
26    /// checks if the element is one
27    fn is_one(x: &Self::T) -> bool
28    where
29        Self::T: PartialEq,
30    {
31        *x == Self::one()
32    }
33    /// additive operaion: $+$
34    fn add(x: &Self::T, y: &Self::T) -> Self::T {
35        <Self::Additive as Magma>::operate(x, y)
36    }
37    /// multiplicative operaion: $+$
38    fn mul(x: &Self::T, y: &Self::T) -> Self::T {
39        <Self::Multiplicative as Magma>::operate(x, y)
40    }
41
42    fn add_assign(x: &mut Self::T, y: &Self::T) {
43        <Self::Additive as Magma>::operate_assign(x, y);
44    }
45
46    fn mul_assign(x: &mut Self::T, y: &Self::T) {
47        <Self::Multiplicative as Magma>::operate_assign(x, y);
48    }
49}
50
51pub trait Ring: SemiRing<Additive: Invertible> {
52    /// additive inverse: $-$
53    fn neg(x: &Self::T) -> Self::T {
54        <Self::Additive as Invertible>::inverse(x)
55    }
56    /// additive right inversed operaion: $-$
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    }
77
78    fn div_assign(x: &mut Self::T, y: &Self::T) {
79        <Self::Multiplicative as Invertible>::rinv_operate_assign(x, y);
80    }
81}
82
83impl<F> Field for F where F: Ring<Multiplicative: Invertible> {}
84
85/// $+,\times$
86pub struct AddMulOperation<T>
87where
88    T: Clone + Zero + One + Add<Output = T> + Mul<Output = T>,
89{
90    _marker: PhantomData<fn() -> T>,
91}
92impl<T> SemiRing for AddMulOperation<T>
93where
94    T: Clone + Zero + One + Add<Output = T> + Mul<Output = T>,
95{
96    type T = T;
97    type Additive = AdditiveOperation<T>;
98    type Multiplicative = MultiplicativeOperation<T>;
99}
competitive/algebra/ring.rs

competitive/algebra/
ring.rs
