algebra/
lib.rs

1//! `Algrebra`では、データ構造に乗せる代数構造のtraitを提供します。
2use std::fmt::Debug;
3
4/// 可換  
5pub trait Commutative {}
6
7/// 作用  
8/// 作用自体もモノイドであることを要求  
9/// 作用素を合成させてから作用させるのと、作用素を一つ一つ作用させる結果が同じであることを要求
10pub trait Action: Debug + Clone {
11    /// 作用の対象
12    type Target: Clone;
13    /// 恒等写像
14    fn id_action() -> Self;
15    /// 作用の合成(selfが先、rhsが後)  
16    /// (atcoder libraryとは作用の順が逆なので注意)
17    fn composition(&mut self, rhs: &Self);
18    /// 作用の適用
19    fn apply(&self, target: &mut Self::Target);
20}
21
22/// モノイド
23pub trait Monoid: Debug {
24    /// モノイドの要素
25    type Target: Debug + Clone;
26    /// 単位元
27    fn id_element() -> Self::Target;
28    /// 二項演算
29    fn binary_operation(a: &Self::Target, b: &Self::Target) -> Self::Target;
30}
31
32/// 自己準同型性を要求  
33/// つまり区間和への適用と、各要素への適用の区間和が一致することを要求  
34pub trait ActionMonoid {
35    /// 作用の対象のモノイド
36    type M: Monoid;
37    /// 作用素のモノイド
38    type A: Action<Target = <Self::M as Monoid>::Target>;
39}
40
41/// 冪等なモノイド  
42/// つまり x = x op x が成り立つようなモノイド  
43/// SparseTableに乗る
44pub trait IdempotentMonoid: Monoid {}
45
46/// 群   
47/// モノイドに加えて、逆元を持つ  
48pub trait Group: Monoid {
49    fn inverse(a: &Self::Target) -> Self::Target;
50}
51
52/// 半環  
53/// 加算は可換モノイド  
54/// 乗算はモノイド  
55/// 乗算は加法に対して分配法則を満たす a*(b+c) = a*b + a*c, (a+b)*c = a*c + b*c  
56/// 加算の単位元は乗算の零元 0*a=a*0=0
57pub trait Semiring: Debug + Clone + Eq {
58    type Target: Debug + Clone + Eq;
59    fn zero() -> Self::Target;
60    fn one() -> Self::Target;
61    fn add_assign(a: &mut Self::Target, b: &Self::Target);
62    fn mul(a: &Self::Target, b: &Self::Target) -> Self::Target;
63}
algebra/lib.rs

algebra/
lib.rs
