competitive/algebra/
ring.rs

1use super::*;
2use std::{
3    marker::PhantomData,
4    num::Wrapping,
5    ops::{Add, Mul},
6};
7
8pub trait SemiRing {
9    type T: Clone;
10    type Additive: AbelianMonoid<T = Self::T>;
11    type Multiplicative: Monoid<T = Self::T>;
12    /// additive identity: $0$
13    fn zero() -> Self::T {
14        <Self::Additive as Unital>::unit()
15    }
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    fn is_one(x: &Self::T) -> bool
27    where
28        Self::T: PartialEq,
29    {
30        *x == Self::one()
31    }
32    /// additive operaion: $+$
33    fn add(x: &Self::T, y: &Self::T) -> Self::T {
34        <Self::Additive as Magma>::operate(x, y)
35    }
36    /// multiplicative operaion: $+$
37    fn mul(x: &Self::T, y: &Self::T) -> Self::T {
38        <Self::Multiplicative as Magma>::operate(x, y)
39    }
40
41    fn try_matrix_product(_a: &[Vec<Self::T>], _b: &[Vec<Self::T>]) -> Option<Vec<Vec<Self::T>>> {
42        None
43    }
44
45    fn dot_product(x: &[Self::T], y: &[Self::T]) -> Self::T {
46        assert_eq!(x.len(), y.len());
47        x.iter().zip(y).fold(Self::zero(), |mut sum, (x, y)| {
48            Self::add_assign(&mut sum, &Self::mul(x, y));
49            sum
50        })
51    }
52
53    fn add_scaled_assign(x: &mut [Self::T], y: &[Self::T], a: &Self::T) {
54        assert_eq!(x.len(), y.len());
55        for (x, y) in x.iter_mut().zip(y) {
56            Self::add_assign(x, &Self::mul(a, y));
57        }
58    }
59
60    fn add_assign(x: &mut Self::T, y: &Self::T) {
61        <Self::Additive as Magma>::operate_assign(x, y);
62    }
63
64    fn mul_assign(x: &mut Self::T, y: &Self::T) {
65        <Self::Multiplicative as Magma>::operate_assign(x, y);
66    }
67}
68
69pub trait Ring: SemiRing<Additive: Invertible> {
70    /// additive inverse: $-$
71    fn neg(x: &Self::T) -> Self::T {
72        <Self::Additive as Invertible>::inverse(x)
73    }
74    /// additive right inversed operaion: $-$
75    fn sub(x: &Self::T, y: &Self::T) -> Self::T {
76        <Self::Additive as Invertible>::rinv_operate(x, y)
77    }
78
79    fn sub_assign(x: &mut Self::T, y: &Self::T) {
80        <Self::Additive as Invertible>::rinv_operate_assign(x, y);
81    }
82}
83
84impl<R> Ring for R where R: SemiRing<Additive: Invertible> {}
85
86pub trait Field: Ring<Multiplicative: Invertible> {
87    /// multiplicative inverse: $-$
88    fn inv(x: &Self::T) -> Self::T {
89        <Self::Multiplicative as Invertible>::inverse(x)
90    }
91    /// multiplicative right inversed operaion: $-$
92    fn div(x: &Self::T, y: &Self::T) -> Self::T {
93        <Self::Multiplicative as Invertible>::rinv_operate(x, y)
94    }
95
96    fn div_assign(x: &mut Self::T, y: &Self::T) {
97        <Self::Multiplicative as Invertible>::rinv_operate_assign(x, y);
98    }
99}
100
101impl<F> Field for F where F: Ring<Multiplicative: Invertible> {}
102
103pub trait DotProduct: Sized + Clone + Zero + Add<Output = Self> + Mul<Output = Self> {
104    fn try_matrix_product(_a: &[Vec<Self>], _b: &[Vec<Self>]) -> Option<Vec<Vec<Self>>> {
105        None
106    }
107
108    fn add_scaled_assign(x: &mut [Self], y: &[Self], a: &Self) {
109        assert_eq!(x.len(), y.len());
110        for (x, y) in x.iter_mut().zip(y) {
111            *x = x.clone() + a.clone() * y.clone();
112        }
113    }
114
115    fn dot_product(x: &[Self], y: &[Self]) -> Self {
116        assert_eq!(x.len(), y.len());
117        x.iter()
118            .zip(y)
119            .fold(Self::zero(), |sum, (x, y)| sum + x.clone() * y.clone())
120    }
121}
122
123macro_rules! impl_dot_product {
124    ($($t:ty)*) => {
125        $(impl DotProduct for $t {})*
126    };
127}
128impl_dot_product!(u8 u16 u32 u64 usize u128 i8 i16 i32 i64 isize i128 f32 f64);
129
130impl<T> DotProduct for Wrapping<T> where
131    Wrapping<T>: Clone + Zero + Add<Output = Wrapping<T>> + Mul<Output = Wrapping<T>>
132{
133}
134
135/// $+,\times$
136pub struct AddMulOperation<T>
137where
138    T: DotProduct + One,
139{
140    _marker: PhantomData<fn() -> T>,
141}
142impl<T> SemiRing for AddMulOperation<T>
143where
144    T: DotProduct + One,
145{
146    type T = T;
147    type Additive = AdditiveOperation<T>;
148    type Multiplicative = MultiplicativeOperation<T>;
149
150    #[inline]
151    fn try_matrix_product(a: &[Vec<T>], b: &[Vec<T>]) -> Option<Vec<Vec<T>>> {
152        T::try_matrix_product(a, b)
153    }
154
155    #[inline]
156    fn dot_product(x: &[Self::T], y: &[Self::T]) -> Self::T {
157        T::dot_product(x, y)
158    }
159
160    #[inline]
161    fn add_scaled_assign(x: &mut [Self::T], y: &[Self::T], a: &Self::T) {
162        T::add_scaled_assign(x, y, a);
163    }
164}
competitive/algebra/ring.rs

competitive/algebra/
ring.rs
