代数的構造の例

半群・モノイド・群

半群（結合法則を満たす $ (x * y) * z = x * (y * z)）に

単位元がある（ $ x * e = e * x = x）とモノイドになる

さらに逆元がある（ $ x * x^{-1} = x^{-1} * x = e）と群になる

半群に適当な単位元を付け加えるとモノイドになる

モノイドを群にするのは無理（多分）

テクニック

半群の演算の繰返し$ \underbrace{a*a*\cdots*a}_{n}はバイナリー法で$ O(\log n)で計算できる

モノイドはセグメント木に乗せると区間演算クエリ$ a_l * a_{l + 1} * \cdots * a_{r}を前処理$ O(n)、クエリ$ O(\log n)で計算できる

遅延セグメント木なら区間更新クエリ（半環である必要がある？）も$ O(\log n)で計算できる

例

和（整数、実数、行列など、群）

積（整数、実数、行列積、ベクトルの内積など、群だったりモノイドだったりする）

$ \min, \max（整数、実数）

$ \gcd, \text{lcm}（素因数的に考えると$ \min, \max）

$ \text{and}, \text{or}（ビットごとの$ \min, \max）

$ \text{xor}（これは群）

$ \frac{ab}{a+b}（実数なら半群、単位元として$ \inftyを入れればモノイド）

$ ((\N, \N), \oplus): モノイド

これは数の文字列としての結合、$ 1番目は値、$ 2番目は桁数

$ (a, b) \oplus (c, d) = (a \times 10^d + c, b + d)

一次関数の合成$ f(x) = ax + b

$ f(x) = ax + b

$ g(x) = cx + d

$ f\circ g(x) = (ac)x + (ad + b)

二次関数以上は合成すると次数が大きくなるので無理、多項式ならOK？

$ f(x) = a_n x^n + \cdots + a_1 x + a_0

$ g(x) = b_m x^m + \cdots + b_1 x + b_0

$ f\circ g(x) = c_{n + m} x^{n + m} + \cdots + c_1 x + c_0（FFTで畳み込みをすると$ O((n + m) \log (n + m))で計算できる）

（半）環

$ (\mathbb C, +, \times): 環

$ (\R, \min, +): 半環

$ (\R, \max, +): 半環

$ (\R, \min, \max): 束

$ (\R, \max, \min): 束

$ ((\mathbb C, \mathbb C), \oplus, \otimes): 環

$ (a, b) \oplus (c, d) = (a + c, b + d)

$ (a, b) \otimes (c, d) = (ad + bc, bd)

圏

なんだっけ

例

グラフ上のパスの連結: $ (t \to u) + (u \to v) = (t \to v)

行列累乗でパスを数え上げたりするときに使える（行列積）