AC自动机
一、算法实现
1 |
|
有序表
发表于
更新于
一、算法实现
1、平衡二叉树
1 | // https://www.luogu.com.cn/problem/P3369 |
1、Treap(有旋)
1 | // https://www.luogu.com.cn/problem/P3369 |
群论基础
发表于
更新于
群论基础
一、群的定义及性质
1、定义
1）若$V=<S, ·>$ 是代数系统，如果$·$是可结合的，称$V$为半群。
2）若$V=<S, ·>$ 存在单位元$e$，则称$V$是幺半群或独异点。
3）若$V=<S, ·>$ 是独异点， 若$\forall a \in S$ 有 $a^{-1} \in S$, 则称$V$为群， 通常记为$G$。
4）若群$G$是有穷集， 则称$G$为有限群，否则称为无限群，群$G$的基数成为群$G$阶。
5）只含有单位元的群称作平凡群。
6）若群$G$中的二元运算是可交换的，则称$G$为交换群或阿贝尔（Abel）群。
7）设$G$是群，$a \in G$， 使得等式$a^{k} = e$成立的最小正整数$k$称为$a$的阶（或者周期），记作$|a|=k$, 这时也称$a$为$k$阶元，若不存在这样的正整数$k$，则称$a$为无限阶元。
2、定理
1）$\forall a \in G, a^{-1}$ 唯一。
2）$\forall a \in G, (a^{-1})^{-1} = a$。
3）$\forall a,b \in G, (ab)^{-1} = b^{-1}a^{-1}$。
4）$\forall a \in G, n,m \in Z, (a)^{n}(a)^{m} =a^{n+m}$。
5）$\forall a \in G, n,m \in Z,(a^{n})^{m} =a^{nm}$。
6）若$G$为交换群，则$(ab)^{n} = a^{n}b^{n}$。
7）$\forall a,b,c \in G$，若$ab = ac$ 则 $b=c$。
8）$\forall a,b,c \in G$，若$ba = ca$ 则 $b=c$。
9）若$a \in G$，且$|a|=r$, 设$k$是整数、则$a^{k} = e$ 当且仅当 $r|k$。
10）若$a \in G$，且$|a|=r$, 则$|a^{-1}| = |a|$。
1-8根据定义容易证明，下面证明9：
充分性：因为$r|k, a^{r}=e$， 所以$k = mr$, 则 $a^{k} = a^{mr} = (a^{r})^{m} = e^{m} = e$。
必要性：因为$a^{k}=e, a^{r}=e,r \le k$，所以有$k=mr+i(0 \le i \lt r), e = a^{k} = a^{mr+i} = a^{mr}a^{i}$，$i$ 必须等于0。
下面证明10：
$(a^{-1})^{r} = e$， 设$|a^{-1}| = t$, 则 $t|r$, 这说明$a$的逆元的阶是$a$的阶的因子，又$a$的逆和$a$互逆，所以有 $r|t$, 所以$r=t$。
也可以考虑对称展开（在例题1有所体现）：
$(a^{-1})^{r} = e$， 设$|a^{-1}| = t$, 得到 $t|r$， 又$((a^{-1})^{-1})^{t}=((a^{-1})^{t})^{-1}=e, |((a^{-1})^{-1})| = r$ 得到$r=t$。
因此 $|a^{-1}| = |a|$。
3、例题
1）$\forall a,b \in G$ 是有限阶元，证明：$|b^{-1}ab|=|a|$。
证明：
设$|a|=r, |b^{-1}ab|=t$，则有：
$$
\begin{alignedat}{1}
(b^{-1}ab)^r &= (b^{-1}ab)(b^{-1}ab)…(b^{-1}ab) \
&= (b^{-1}a^{r}b) \
&= e
\end{alignedat}
$$
因此$t|r$。
另一方面，$a=b(b^{-1}ab)b^{-1}$，则：
$$
\begin{alignedat}{1}
(a)^t &= (b(b^{-1}ab)b^{-1})(b(b^{-1}ab)b^{-1})…(b(b^{-1}ab)b^{-1}) \
&= (b^{-1}(b^{-1}ab)^{t}b) \
&= e
\end{alignedat}
$$
因此$r|t$。
所以 $|b^{-1}ab|=|a|$。
2）$G$ 是有限阶元，证明：$G$ 中阶大于2的元素有偶数个。
证明：显然阶大于2的元素与它的逆不相同且成对出现。
二、子群与群的陪集分解
1、定义
1）设$G$是群，$H$是$G$的非空子集，如果$H$关于$G$中的运算构成群，则称$H$是$G$的子群，记作$H \le G$。
2）若$H$是$G$的子群，且$H \subset G$，则称$H$是$G$的真子群，记作$H \lt G$。
3）设$G$是群，$a \in G$，$a$所有的幂构成的集合称作由$a$生成的子群，记作$\lt a \gt$。
4）设$G$是群，$a \in G, \forall b \in G, ab=ba$，所有$a$构成的集合称作群$G$的中心。
5）若$H$是$G$的子群，且$a \in G$，令$Ha={ha|h \in H}$ 称$Ha$是子群$H$在$G$中的右陪集。称$a$为$Ha$的代表元素。
6）若$H$是$G$的子群，且$a \in G$，令$aH={ah|h \in H}$ 称$aH$是子群$H$在$G$中的左陪集。称$a$为$aH$的代表元素。
2、 定理
1）设$G$是群，$H$是$G$的非空子集，$H$是$G$的子群当且仅当：$\forall a,b \in H$ 有 $ab\in H$且$\forall a \in H$有$a^{-1} \in H$。
2）设$G$是群，$H$是$G$的非空子集，$H$是$G$的子群当且仅当：$\forall a,b \in H$ 有 $ab^{-1}\in H$。
3）设$G$是群，$H$是$G$的非空子集，$H$是有穷集，$H$是$G$的子群当且仅当：$\forall a,b \in H$ 有 $ab\in H$。
4）设$G$是群，$H$是$G$的非空子集，$H$是有穷集，$H$是$G$的子群当且仅当：$\forall a,b \in H$ 有 $ab\in H$。
5）设$ G $ 是一个有限群，$ H $ 是 $ G $ 的子群，则 $ |H| $（子群 $ H $ 的阶）是 $ |G| $（群 $ G $ 的阶）的约数，即： $|G| = [G : H] \cdot |H|$ 其中 $ [G : H] $ 是 $ H $ 在 $ G $ 中的 左陪集的个数（拉格朗日定理，不妨设$|H|=m$, 显然$|aH|=m$）。
3、例题
1）设$G$是群，$H$，$K$是$G$的子群， 证明$ H \cap G$也是$G$的子群。
易证，这说明交集部分只包含那些既符合 $H$的封闭性要求、又符合 $K$的封闭性要求的元素。
2）设$G$是群，$H$，$K$是$G$的子群， 证明$ H \cup G$也是$G$的子群，则$ H \subseteq K$ 或 $ K \subseteq H$ 。
证明：任取$h \in H, k \in K, k \notin H$, 若$ H \subseteq K$ 或 $ K \subseteq H$ 不成立，则$hk \notin H$，如若不然，则$hk \in H$ 则 $h^{-1}hk = k \in H$, 同理可得 $hk \notin K$, 矛盾，故结论成立。这说明了两个子群的并集能成为一个新的子群，只有当这两个子群之间有包含关系时。