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
52where
53    Self::Additive: Invertible,
54{
55    /// additive inverse: $-$
56    fn neg(x: &Self::T) -> Self::T {
57        <Self::Additive as Invertible>::inverse(x)
58    }
59    /// additive right inversed operaion: $-$
60    fn sub(x: &Self::T, y: &Self::T) -> Self::T {
61        <Self::Additive as Invertible>::rinv_operate(x, y)
62    }
63
64    fn sub_assign(x: &mut Self::T, y: &Self::T) {
65        <Self::Additive as Invertible>::rinv_operate_assign(x, y);
66    }
67}
68
69impl<R> Ring for R
70where
71    R: SemiRing,
72    R::Additive: Invertible,
73{
74}
75
76pub trait Field: Ring
77where
78    Self::Additive: Invertible,
79    Self::Multiplicative: Invertible,
80{
81    /// multiplicative inverse: $-$
82    fn inv(x: &Self::T) -> Self::T {
83        <Self::Multiplicative as Invertible>::inverse(x)
84    }
85    /// multiplicative right inversed operaion: $-$
86    fn div(x: &Self::T, y: &Self::T) -> Self::T {
87        <Self::Multiplicative as Invertible>::rinv_operate(x, y)
88    }
89
90    fn div_assign(x: &mut Self::T, y: &Self::T) {
91        <Self::Multiplicative as Invertible>::rinv_operate_assign(x, y);
92    }
93}
94
95impl<F> Field for F
96where
97    F: Ring,
98    F::Additive: Invertible,
99    F::Multiplicative: Invertible,
100{
101}
102
103/// $+,\times$
104pub struct AddMulOperation<T>
105where
106    T: Clone + Zero + One + Add<Output = T> + Mul<Output = T>,
107{
108    _marker: PhantomData<fn() -> T>,
109}
110impl<T> SemiRing for AddMulOperation<T>
111where
112    T: Clone + Zero + One + Add<Output = T> + Mul<Output = T>,
113{
114    type T = T;
115    type Additive = AdditiveOperation<T>;
116    type Multiplicative = MultiplicativeOperation<T>;
117}
competitive/algebra/ring.rs

competitive/algebra/
ring.rs
