モノイド | Notion

競プロで出てくるモノイド

環の足し算・掛け算
- $\mathbb{Z}$ の足し算・掛け算
- $\mathbb{Z}/n\mathbb{Z}$ の足し算・掛け算
- 正方行列の足し算・掛け算
- (足し算の方は群だが、掛け算の方は群ではない)
群
- ベクトル空間の足し算
- xor
  - bitwise に $\mathbb{Z}/2\mathbb{Z}$ の足し算をしたもの
- $D_n$ (2面体群)
  - 見たことはない
順序系（有界束）
- min, max
- gcd, lcm
- and, or
  - and, or は bool の論理演算と、整数のビット演算の両方
$\{0,1,...,n-1\}\to\{0,1,...,n-1\}$ の写像全体とその合成
- ダブリング (参照: 累乗・繰り返し二乗法)
１次関数とその合成
ロリハ（ハッシュ値とベース）
- 一般に、10進法での値とその連結はモノイドをなす
LCA
- 単位元はないので、適当に付与する必要がある
- 木に順序を入れたときの sup だと思える。そう考えると gcd, lcm の仲間ぽさがある
自由モノイド
自然数全体とその足し算
- 競プロでは $\mathbb{Z}$ の足し算とみなせば良さそう
自然数全体とその掛け算