Welcome to Liam's Blog
About me
-
My id : lnw143
-
Year of Birth : 2009
-
Location : Zhongshan, Guangdong Province, CHN
Motto
Nothing.
Links
2025 年 8 月（及以前）做题记录
可能会不定时放一些远古时代的题目。
群论基础
定义
定义集合 \(G\) 与在 \(G\) 上的二元运算 \(\times\)，若其满足以下条件，则称 \((G,\times)\) 为一个群。
- 封闭性。\(\forall a,b \in G,a \times b \in G\)
- 结合性。\(\forall a,b,c \in G,(a \times b) \times c = a \times (b \times c)\)
- 单位元存在性。\(\exists e \in G,\forall a \in G,e \times a = a \times e = a\)
- 逆元存在性。\(\forall a \in G,\exists b \in G,a \times b = b \times a = e\)
单位根相关
复数域下方程 \(x^n = 1\) 恰好有 \(n\) 个解，记 \(\omega_n = e^{\frac {2 \text{i} \pi} n}\)，则这 \(n\) 个解恰好为 \(1,\omega_n,\omega_n^2,\cdots,\omega_n^{n-1}\)。我们将 \(\omega_n\) 称作 \(n\) 次单位根。
在运算中，有 \(\omega_n = e^{\frac {2 \text{i} \pi} n} = \cos \frac {2 \pi} n + \text{i} \sin \frac{2 \pi} n\)。
特别地，在模 \(P\) 意义的数域下，有 \(\omega_n \equiv g^{\frac {P-1} n} \pmod P\)，其中 \(g\) 是模 \(P\) 意义下的原根。
Hall 定理
定理内容
对于二分图 \(G=(V,E)\)，设其左、右部点集大小分别为 \(n,m(n \le m)\)。
对于左部点集的任意子集 \(S\)，定义其邻域 \(N(S)\) 为点集内点与右部点相连的点集，即 \(N(S) = \{v|\exists u \in S, (u,v) \in E\}\)。
则该图有完美匹配的充要条件为 \(\forall S,|S| \le |N(S)|\)。
证明
必要性显然，充分性可递归证明。
设当前左部点为 \(S\)，对于 \(u \in S\)，考虑为其寻找一个匹配点。
若 \(N(S\setminus \{u\}) = N(S)\)，任选 \(v \in N(S)\) 作为 \(u\) 的匹配点即可。
否则选择在 \(N(S)\) 中但不在 \(N(S\setminus \{u\})\) 中的点，这些点接下来也没法被匹配，所以不影响下面的过程。
于是我们将问题集合减小了 1，条件不变，递归构造即可。