競技プログラミングのための代数入門

モノイド！（素振り）

なぜ代数をするのか？

代数構造とは、ある性質を持った集合と演算の組に名前をつけたものです。
ある演算そのものに注目するのではなく、より一般にある性質を満たす集合と演算全体に注目することで、その性質を満たすものすべてについての議論を一度に行うことができます。
代数構造はデータ構造とも関連していて、あるデータ構造で扱えるかどうかを代数を用いることで機械的に判定することができます。

例をあげましょう。セグメント木は後述するモノイドを扱うことのできるデータ構造です。
このとき、整数と和や積などの個別の対象がセグメント木で扱えるかどうかをいちいち考える必要はなく、ただ対象がモノイドであるかどうかだけを調べることで判定することができます。

マグマ

集合 M$M$ と二項演算 ∘:M×M→M$\circ :M\times M\to M$ の組 (M,∘)$(M,\circ )$ のこと。
くだけて言うと、 M$M$ の任意の二つの要素の間の演算が定義されていて、その結果もまた M$M$ に含まれるということ。

かなり弱い条件　これを満たしていないと静的型付き言語で実装するのがつらい

マグマではない例：(Z,/)$(\mathbb{Z},/)$
例えば、 1,2∈Z$1,2\in \mathbb{Z}$であるが 1/2∉Z$1/2\notin \mathbb{Z}$ であるから、これはマグマではない
また1,0∈Z$1,0\in \mathbb{Z}$であるが、1/0$1/0$ は定義されていない。

半群

マグマ(M,∘)$(M,\circ )$ であって、結合則を満たすもの
つまり、 任意の a,b,c∈M$a,b,c\in M$ に対して、 (a∘b)∘c=a∘(b∘c)$(a\circ b)\circ c=a\circ (b\circ c)$ を満たすようなもの
結合則を満たしているとき、単に a∘b∘c$a\circ b\circ c$ とも表す。

マグマではあるが半群ではない例：(Z,−)$(\mathbb{Z},-)$
例えば、 1,2,3∈Z$1,2,3\in \mathbb{Z}$であるが (1−2)−3=−4≠1−(2−3)=2$(1-2)-3=-4\ne 1-(2-3)=2$

モノイド

半群(M,∘)$(M,\circ )$ であって、単位元 e∈M$e\in M$ をもつもの。
単位元とは、任意の a∈M$a\in M$ に対して a∘e=e∘a=a$a\circ e=e\circ a=a$を満たすような元のこと。
（厳密には右単位元と左単位元があり、右単位元かつ左単位元であるようなものを単に単位元と呼ぶ）

単位元は存在するなら一意である。
証明： e,e′∈M$e,e^{\prime }\in M$がともに半群(M,∘)$(M,\circ )$の単位元であると仮定する。
e∘e′=e=e′$e\circ e^{\prime }=e=e^{\prime }$（e'が単位元、eが単位元）であるから、一意である。

半群ではあるがモノイドではない例：(N,min)$(\mathbb{N},min)$
もし単位元 e∈N$e\in \mathbb{N}$が min$min$ の単位元であるとすると、 e≠e+1∈N$e\ne e+1\in \mathbb{N}$に対して min(e,e+1)=e≠e+1$min(e,e+1)=e\ne e+1$ であるから矛盾、従って (N,min)$(\mathbb{N},min)$ はモノイドではない

セグメント木はモノイドを扱うことができる。
つまり、あるマグマ(M,∘)$(M,\circ )$が結合的であり単位元をもつなら、それはセグメント木で扱うことができる。
beet-aizu.hatenablog.com

半群からモノイドへの埋め込み

モノイドではない半群(M,∘)$(M,\circ )$に対して、適当な要素 e∉M$e\notin M$を選び、 集合M′=M∪{e}$M^{\prime }=M\cup \{e\}$と演算∘′${\circ }^{\prime }$を以下のように定めると、 (M′,∘′)$(M^{\prime },{\circ }^{\prime })$は e∈M′$e\in M^{\prime }$を単位元とするモノイドとなる。
a∘′b=⎧⎩⎨⎪⎪a          if     b=eb          elif  a=ea∘b     otherwise$a{\circ }^{\prime }b=\{\begin{array}{l}aifb=e\\ belifa=e\\ a\circ botherwise\end{array}$
例： (N,min)$(\mathbb{N},min)$ をモノイドに埋め込む
∞∉N$\mathrm{\infty }\notin \mathbb{N}$に対して、集合M=N∪{∞}$M=\mathbb{N}\cup \{\mathrm{\infty }\}$とすると、 (M,min)$(M,min)$は ∞$\mathrm{\infty }$ を単位元とするモノイドになる。
競技プログラミングでは、十分大きなINFをminの単位元として使うことがあるが、それはこの埋め込みの一例になっている。

群

モノイド(M,∘)$(M,\circ )$ であって、任意の要素について逆元をもつようなもの。
a∘b=e$a\circ b=e$ を満たすとき、bをaの右逆元、aをbの左逆元と呼ぶ。
ただし、群においては左逆元と右逆元は一致し、単に逆元という。
証明： a∘b=e,b∘c=e$a\circ b=e,b\circ c=e$とする
a∘b∘c=(a∘b)∘c=e∘c=c$a\circ b\circ c=(a\circ b)\circ c=e\circ c=c$
a∘b∘c=a∘(b∘c)=a∘e=a$a\circ b\circ c=a\circ (b\circ c)=a\circ e=a$

特に、単位元e$e$ の逆元は単位元e$e$である。
a$a$の逆元を a−1$a^{-1}$と表す。

累積和は群を扱うことができる。
s(x)$s(x)$をx-1までの累積和として、半開区間 [l,r)$[l,r)$に対し f(l,r)=s(l)−1∘s(r)$f(l,r)=s(l{)}^{-1}\circ s(r)$ とすればよい。
概略：
(a∘b)−1=(a∘b)−1∘e=(a∘b)−1∘(a∘e∘a−1)=(a∘b)−1∘(a∘b∘b−1∘a−1)=(a∘b)−1∘(a∘b)∘(b−1∘a−1)=((a∘b)−1∘(a∘b))∘(b−1∘a−1)=e∘(b−1∘a−1)=b−1∘a−1$$\begin{gathered} (a\circ b{)}^{-1}=(a\circ b{)}^{-1}\circ e=(a\circ b{)}^{-1}\circ (a\circ e\circ a^{-1}) \\ =(a\circ b{)}^{-1}\circ (a\circ b\circ b^{-1}\circ a^{-1})=(a\circ b{)}^{-1}\circ (a\circ b)\circ (b^{-1}\circ a^{-1}) \\ =((a\circ b{)}^{-1}\circ (a\circ b))\circ (b^{-1}\circ a^{-1})=e\circ (b^{-1}\circ a^{-1})=b^{-1}\circ a^{-1} \end{gathered}$$

アーベル群

群(M,∘)$(M,\circ )$ であって、可換則を満たすようなもの。
つまり、任意の a,b∈M$a,b\in M$ に対して、 a∘b=b∘a$a\circ b=b\circ a$ を満たすようなもの。

群ではあるがアーベル群ではない例 ：二次正則行列とその積
例えば、
(1110)∘(1011)=(1121)${\displaystyle \left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)\circ \left(\begin{array}{cc}1& 1\\ 0& 1\end{array}\right)=\left(\begin{array}{cc}1& 2\\ 1& 1\end{array}\right)}$
であるが、
(1011)∘(1110)=(2110)${\displaystyle \left(\begin{array}{cc}1& 1\\ 0& 1\end{array}\right)\circ \left(\begin{array}{cc}1& 1\\ 1& 0\end{array}\right)=\left(\begin{array}{cc}2& 1\\ 1& 0\end{array}\right)}$
であるから、可換ではない。

Binary Indexed Treeはアーベル群を扱うことができる。

TODO: 書く

環

整域

体