cp_library_rs/algebraic_structure/
monoid_with_context.rs

1//! ## モノイド
2//!
3//! - [`Monoid::Val`] ： データの型 $`S`$
4//! - [`Monoid::e`] ： 単位元を返す関数 $`\varnothing \to S`$
5//! - [`Monoid::op`] ： 演算 $`S\times S \to S`$
6
7/// モノイド
8///
9/// - [`Monoid::Val`] ： データの型 $`S`$
10/// - [`Monoid::e`] ： 単位元を返す関数 $`\varnothing \to S`$
11/// - [`Monoid::op`] ： 演算 $`S\times S \to S`$
12pub trait MonoidCtx {
13    /// データの型 （$`S`$）
14    type Val: Clone;
15    /// 単位元 （$`\varnothing \to S`$）
16    fn e(&self) -> Self::Val;
17    /// 演算 （$`S \times S \to S`$）
18    fn op(&self, left: &Self::Val, right: &Self::Val) -> Self::Val;
19}
20
21// ========== 実装 ==========
22
23pub mod examples {
24    use std::ops::{Add, Mul, Rem};
25
26    use num::{One, Zero};
27
28    use crate::algebraic_structure::monoid_with_context::MonoidCtx;
29
30    /// 法が与えられる区間和
31    pub struct AddMod<T>(pub T);
32
33    impl<T> MonoidCtx for AddMod<T>
34    where
35        T: Clone + Zero + Add + Rem<Output = T>,
36    {
37        type Val = T;
38        fn e(&self) -> Self::Val {
39            T::zero()
40        }
41        fn op(&self, left: &Self::Val, right: &Self::Val) -> Self::Val {
42            (left.clone() + right.clone()) % self.0.clone()
43        }
44    }
45
46    /// 法が与えられる区間積
47    pub struct MulMod<T>(pub T);
48
49    impl<T> MonoidCtx for MulMod<T>
50    where
51        T: Clone + One + Mul + Rem<Output = T>,
52    {
53        type Val = T;
54        fn e(&self) -> Self::Val {
55            T::one()
56        }
57        fn op(&self, left: &Self::Val, right: &Self::Val) -> Self::Val {
58            (left.clone() * right.clone()) % self.0.clone()
59        }
60    }
61}
cp_library_rs/algebraic_structure/monoid_with_context.rs

cp_library_rs/algebraic_structure/
monoid_with_context.rs
