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    /// multiplicative identity: $1$
16    fn one() -> Self::T {
17        <Self::Multiplicative as Unital>::unit()
18    }
19    /// additive operaion: $+$
20    fn add(x: &Self::T, y: &Self::T) -> Self::T {
21        <Self::Additive as Magma>::operate(x, y)
22    }
23    /// multiplicative operaion: $+$
24    fn mul(x: &Self::T, y: &Self::T) -> Self::T {
25        <Self::Multiplicative as Magma>::operate(x, y)
26    }
27
28    fn add_assign(x: &mut Self::T, y: &Self::T) {
29        <Self::Additive as Magma>::operate_assign(x, y);
30    }
31
32    fn mul_assign(x: &mut Self::T, y: &Self::T) {
33        <Self::Multiplicative as Magma>::operate_assign(x, y);
34    }
35}
36
37pub trait Ring: SemiRing
38where
39    Self::Additive: Invertible,
40{
41    /// additive inverse: $-$
42    fn neg(x: &Self::T) -> Self::T {
43        <Self::Additive as Invertible>::inverse(x)
44    }
45    /// additive right inversed operaion: $-$
46    fn sub(x: &Self::T, y: &Self::T) -> Self::T {
47        <Self::Additive as Invertible>::rinv_operate(x, y)
48    }
49
50    fn sub_assign(x: &mut Self::T, y: &Self::T) {
51        <Self::Additive as Invertible>::rinv_operate_assign(x, y);
52    }
53}
54
55impl<R> Ring for R
56where
57    R: SemiRing,
58    R::Additive: Invertible,
59{
60}
61
62pub trait Field: Ring
63where
64    Self::Additive: Invertible,
65    Self::Multiplicative: Invertible,
66{
67    /// multiplicative inverse: $-$
68    fn inv(x: &Self::T) -> Self::T {
69        <Self::Multiplicative as Invertible>::inverse(x)
70    }
71    /// multiplicative right inversed operaion: $-$
72    fn div(x: &Self::T, y: &Self::T) -> Self::T {
73        <Self::Multiplicative as Invertible>::rinv_operate(x, y)
74    }
75
76    fn div_assign(x: &mut Self::T, y: &Self::T) {
77        <Self::Multiplicative as Invertible>::rinv_operate_assign(x, y);
78    }
79}
80
81impl<F> Field for F
82where
83    F: Ring,
84    F::Additive: Invertible,
85    F::Multiplicative: Invertible,
86{
87}
88
89/// $+,\times$
90pub struct AddMulOperation<T>
91where
92    T: Clone + Zero + One + Add<Output = T> + Mul<Output = T>,
93{
94    _marker: PhantomData<fn() -> T>,
95}
96impl<T> SemiRing for AddMulOperation<T>
97where
98    T: Clone + Zero + One + Add<Output = T> + Mul<Output = T>,
99{
100    type T = T;
101    type Additive = AdditiveOperation<T>;
102    type Multiplicative = MultiplicativeOperation<T>;
103}
competitive/algebra/ring.rs

competitive/algebra/
ring.rs
