逻辑
1. 充分条件、必要条件与充要条件的概念
若 \(p\Rightarrow q\)，则 \(p\) 是 \(q\) 的充分条件，\(q\) 是 \(p\) 的必要条件。
\(p\) 是 \(q\) 的充分不必要条件，\(p\Rightarrow q\) 且 \(q\not\Rightarrow p\)。
\(p\) 是 \(q\) 的必要不充分条件，\(p\not\Rightarrow q\) 且 \(q\Rightarrow p\)。
\(p\) 是 \(q\) 的充要条件，\(p\Leftrightarrow q\)。
2. 全称量词和存在量词
全称量词：\(\forall\)。
存在量词：\(\exists\)。
集合
1. 集合与元素
集合元素的三个特征：确定性、互异性、无序性。
元素与集合的关系是属于或不属于关系，用符号 \(\in\) 或 \(\notin\) 表示。
集合的表示法：列举法、描述法、图示法。
自然数集：\(N\)，正整数集：\(N^*\) 或 \(N_+\)，整数集：\(Z\)，有理数集：\(Q\)，实数集：\(R\)。
2. 集合间的基本关系
子集：集合 \(A\) 中所有元素都在集合 \(B\) 中，\(A\subseteq B\)。
真子集：集合 \(A\) 是 \(B\) 的子集，且集合 \(B\) 中至少有一个元素不在集合 \(A\) 中，\(A\subsetneq B\)。
集合相等：集合 \(A\)，\(B\) 中元素相同，\(A=B\)。
3. 集合的基本运算
集合的并集：\(A\cup B={x|x\in A 或 x\in B}\)。
集合的交集：\(A\cap B={x|x\in A 且 x\in B}\)。
集合的补集：\(\complement_UA={x|x\in U 且 x\notin A}\)。
结合律：对于任意三个集合 \(A\)，\(B\) 和 \(C\)，结合律指的是 \((A ∪ B) ∪ C = A ∪ (B ∪ C)\) 和 \((A ∩ B) ∩ C = A ∩ (B ∩ C)\)。
交换律：对于任意两个集合 \(A\) 和 \(B\)，交换律指的是 \(A ∪ B = B ∪ A\) 和 \(A ∩ B = B ∩ A\)。
对称差：\(A \Delta B = (A - B) ∪ (B - A)\)
计数（映射）
1. 映射的概念
两集合 \(A\)，\(B\)：\(A\)，\(B\) 是两个非空集合。
对应关系 \(f\)：\(A\rightarrow B\)，如果按照某种确定的对应关系 \(f\)，使对于集合 \(A\) 中的任意一个元素 \(x\)，在集合 \(B\) 中都有唯一确定的元素 \(f(x)\) 与之对应。
名称：称 \(f\)：\(A\rightarrow B\) 为从集合 \(A\) 到 \(B\) 的一个映射。
2. 映射的有关概念
若 \(f(A)=B\)，则映射 \(f\) 称为满射；若对于 \(A\) 中任意两个不同的元素 \(x_1\not=x_2\)，均有 \(f(x_1)\not=f(x_2)\)，则映射 \(f\) 称为单射；如果映射 \(f\) 既是单射又是满射，则映射 \(f\) 称为一一映射。此时存在 \(f^{-1}\) ：\(B\rightarrow A\)，使得 \(\forall x\in A\)，均有 \(f^{-1}(f(x))=x\)，\(\forall y\in B\)，均有 \(f(f^{-1}(y))=y\)。
3. 映射的应用
\(C_n^k=\frac{n!}{k!(n-k)!}\)
\(C_n^k=C_n^{n-k}\)
\(C_n^0+C_n^1+C_n^2+\cdots +C_n^n=2^n\)
\(C_n^0+C_n^2+C_n^4+\cdots +C_n^{2k}=C_n^1+C_n^3+C_n^5+\cdots+C_n^{2k+2}\)
\(C_n^k=C_{n-1}^k+C_{n-1}^{k-1}\)
\(C_n^k=\frac{n}{k}C_{n-1}^{k-1}\)
\(C_n^k=\frac{n-k+1}{k}C_n^{k-1}\)
容斥
\(|\cup_{i=1}^{n}A_i|=\sum_{i}|A_i|-\sum_{i,j}|A_i\cap A_j|+\sum_{i,j,k}|A_i\cap A_j\cap A_k|\cdots+(-1)^{n-1}\times|\cap_{i=1}^{n}A_i|=\sum\limits_{k=1}^{n}(-1)^{k-1}\times \sum\limits_{1\le x_1\le x_2\cdots x_k\le n}|\cap_{i=1}^{k}A_{x_i}|\)
数列
等差数列：\(a_n=a_1+(n-1)d=dn+(a_1-d)\)，\(s_n=\frac{(a_1+a_n)n}{2}=na_1+\frac{n(n-1)}{2}d\)
等比数列：\(a_n=a_1q^{n-1}(q\not=0)\)，\(s_n=\frac{a_1(1-q^n)}{1-q}(q\not=1)\)，\(s_n=na_1(q=1)\)
裂项
\(\sum\limits_{i=1}^{n}i=\frac{1}{2}n(n+1)\)
\(\sum\limits_{i=1}^{n}i^2=\frac{1}{6}n(n+1)(2n+1)\)
\(\sum\limits_{i=1}^{n}i^3=\frac{1}{4}n^2(n+1)^2\)
\(\sum\limits_{i=0}^{n}C_n^ia^ib^{n-i}=(a+b)^n\)
Abel恒等式
\(\sum\limits_{a_i}^{b_i}=S_nb_n+\sum\limits_{i}^{n-1}S_i(b_{i+1}-b_i)\)
数学归纳法
1. 第一归纳法
- 先证 \(n=1\) 时，成立
- 若 \(n=k\) 时，成立
- 再证 \(n=k+1\) 时，成立
2. 第二归纳法
- 先证 \(n=1\) 时，成立
- 若 \(n=1, n=2, \cdots n=k\) 时，成立
- 再证 \(n=k+1\) 时成立
3. 第三归纳法（证明 \(n\) 元均值不等式）
- 先证 \(n=2\) 时，成立
- 若 \(n=2^k\) 时，成立
- 再证 \(n=2^m\) 时，成立
- 若 \(n = m\) 时，成立
- 最后证 \(n=m-1\) 时，成立
博弈论
- 先求第一制胜点
- 递推：\((1)\) 能走到制胜点的点都是必败点。
\((2)\) 无论怎么走都是必败点，才是必胜点。 - 根据递推的结果猜测策略
- 用数学归纳法证明此策略
汉诺塔
令 \(n\) 为当前汉诺塔的个数，且均在第一根柱子上。
则先将上面 \(n-1\) 个，按顺序移动到第二根柱子上。
再将第 \(n\) 个汉诺塔移动到第三根柱子上。
最后将 \(n - 1\) 个汉诺塔，按顺序移动到第三根柱子上。
于是递推公式即为：\(a_n=2a_{n-1}+1\)。
转变为通项公式即为：\(a_n=2^n-1\)。
砝码问题
只有一边放置砝码，有 \(n\) 个砝码，则最多能够称出 \(2^n-1\) 种重量。
两边都可以放置砝码，有 \(n\) 个砝码，则最多能够称出 \(\frac{3^n-1}{2}\) 种重量。
错排
\(n\) 元错排公式：\(D_n=\sum\limits_{i=0}^{n}(-1)^iC_n^i(n-i)!=\sum\limits_{i=0}^{n}(-1)^i\frac{n!}{i!}=n!\sum\limits_{i=0}^{n}(-1)^i\frac{1}{i!}\approx \frac{n!}{e}\)
递推式：\(D_n=(n-1)(D_{n-1}+D_{n-2})\)
卡特兰数
递推式：\(H_n=\sum\limits_{i=0}^{n}H_iH_{n-i}\)
通项公式：\(H_n=C_{2n}^{n}-C_{2n}^{n-1}=\frac{C_{2n}^{n}}{n+1}\)
递推公式向通项公式的转化
1. 待定系数
递推式两边同时 \(+k\)，再利用第一项和等比数列公式求出通项公式。
最终通项公式为：\(a_n=2^n-1\)
2. 两边同除以 \(p^{n+1}\)
递推式两边同时除以 \(p^{n+1}\)，再利用第一项和等差数列公式求出通项公式。
最终通项公式为：\(a_n=2^n-1\)
3. 取倒数
递推式两边同时取倒数，再利用第一项和等比数列公式或等差数列公式求出通项公式。
4. fib
当有 \(n+1\) 项与 \(n\) 和 \(n-1\) 有关系时，将第 \(k\) 项转换为 \(x^{k}\)，再利用前两项求得系数。
斐波那契通项公式：$$\frac{\sqrt[]{5}}{5}((\frac{1+\sqrt[]{5}}{2})n-(\frac{1-\sqrt[]{5}}{2})n)$$
Stirling 数
第一斯特林数：\(S(p, i)=S(p-1, i-1)+iS(p-1,i)\) \((1\le i\le p-1)\)
第二斯特林数：\(S(p,i)=S(p-1, i-1)+(p-1)S(p-1, i)\)
Bell 数
\(B_p=\sum\limits_{i=0}^{p}S(p, i)\)
\(B_p=\sum\limits_{i=0}^{p-1}C_{p-1}^{i}B_{p-i-1}\)
整除
1. 定义
\(a|b:\exists n\in Z\) 使得 \(b=an\)。
2. 性质
传递性：\(a|b, b|c\Rightarrow a|c\)
可加减性：\(n|a, n|b\Rightarrow n|a\pm b\)
可乘性：\(a|b, c|d\Rightarrow ac|bd\) \((a|b\Rightarrow a|bd)\)
最大公因与最小公倍
1. 定义
\(\gcd(a, b):\max(m\mid m|a 且 m|b)\)
\(\operatorname{lcm}(a, b):\min(n\mid a|n 且 b|n, n\gt 0)\)
2. 带余除法
\(a\div b=q\cdots r\)
确定了 \(a\) 和 \(b\)，那么 \(q\) 和 \(r\) 就确定了。
3. 辗转相除
\((1)\) \((a, b)=(a-b, b)\)
\(\forall x\in\lbrace a, b的公因数\rbrace\)
\(x|a, x|b\Rightarrow x|a-b\Rightarrow x\in\lbrace a-b与b的公因数\rbrace\)
\(\therefore\lbrace a, b的公因数\rbrace =\lbrace a-b与b的公因数\rbrace\)
\((2)\) 若 \(a\div b=q\cdots r\)，则 \((a, b)=(b, r)\)
证明：通过 \((1)\) 多做几次就好了。
\((3)\) 辗转相除法
令 $$a_2=b_1, b_2=r, a_2\div b_2=q_2\cdots r_2$$ $$(a_2, b_2)=(b_2, r_2)$$
直到 $$r_n=0\ 时，(a_n, b_n)=b_n$$
4. 裴蜀定理
\(ax+by=(a, b)\)
5. \(\gcd\) 的性质
\((a, b, c)=((a, b), c)\)
\((a, b)=(a, b, ax)\)
\((a, b, c)=((a, b), (a, c))\)
6. \(\gcd\) 的重要式子
已知 \(a, b\) 为正整数，\((2^a-1, 2^b-1)=2^{(a, b)}-1\)
已知 \(a, b\) 为正整数，\((2^{2^a}+1, 2^{2^b}+1)=1\)
算术基本定理
1. 质数的定义
\(p\ge 2, n|p\Rightarrow n=1 \ 或 \ n=p\)
2. 分解质因数
一个大于 \(1\) 的正整数 \(n\) 可以分解为若干个质数的乘积，若不考虑质因子之间的顺序，这种分解方式是唯一的。
3. \(v_p(n)\)
\(v_p(n)\) 表示 \(n\) 的标准分解式中所含质因子 \(p\) 的指数。
\(v_p(n_1n_2)=v_p(n_1)+v_p(n_2)\)
\(v_p(\gcd(n_1, n_2))=\min(v_p(n_1), v_p(n_2))\)
\(v_p(\operatorname{lcm}(n_1, n_2))=\max(v_p(n_1), v_p(n_2))\)
4. 因数个数与因数和
设正整数 \(n\) 的标准分解式为： \(n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}\)
因数个数公式：\(d(n)=(e_1+1)(e_2+1)\cdots (e_k+1)\)
因数和公式：\(\sigma(n)=\frac{p_1^{e_1+1}-1}{p_1-1}\frac{p_2^{e_2+1}-1}{p_2-1}\cdots \frac{p_k^{e_k+1}-1}{p_k-1}\)
因数积：\(n^\frac{d(n)}{2}\)
5. \(\gcd\) 的性质
\((ma, mb)=m(a, b)\)
\((a, uv)=(a, (a, u)v)\)
\((u, v)=1\Rightarrow (a, uv)=(a, u)(a, v)\)
6. \(mn\) 与 \(\gcd\) 和 \(\operatorname{lcm}\) 的关系
\((m, n)\times [m, n]=mn\)
同余
1. 定义
\(n|a-b\Rightarrow a\equiv b\pmod n\)
2. 性质
若 \(a\equiv b\pmod n\)，则 \(a\) 与 \(b\) 对 \(n\) 作带余除法所得的余数相同。
自反性：\(a\equiv b\pmod n\Rightarrow b\equiv a\pmod n\)
传递性：\(a\equiv b\pmod n, b\equiv c\pmod n\Rightarrow a\equiv c\pmod n\)
可加减性：\(a_1\equiv a_1\pmod n, b_1\equiv b_2\pmod n\Rightarrow a_1\pm b_1 \equiv a_2\pm b_2\pmod n\)
可乘性：\(a_1\equiv a_1\pmod n, b_1\equiv b_2\pmod n\Rightarrow a_1\times b_1 \equiv a_2\times b_2\pmod n\)
可除性：\(ka\equiv kb\pmod n\Rightarrow a\equiv b\pmod n\)
互质可除性：\(ka\equiv kb\pmod n, (k, n)=1\Rightarrow a\equiv b\pmod n\)
3. 特殊数的余数特征
若 \(m|10^k\)，\(n=a\cdot 10^k+b\)（其中 \(b\) 为 \(n\) 的末 \(k\) 位数，则 \(n\equiv b\pmod m\)
若 \(m|10^k-1\)，\(n=a_s\cdot 10^{sk} +a_{s-1}\cdot 10^{(s-1)k}+\cdots +a_1\cdot 10^k+a_0\)，其中 \(a_s, a_{s-1}, \cdots , a_0\) 均小于 \(10^k\)。则 \(n\equiv a_s+a_{s-1}+\cdots +a_0\pmod m\)
若 \(m|10^k+1\)，\(n=a_s\cdot 10^{sk} +a_{s-1}\cdot 10^{(s-1)k}+\cdots +a_1\cdot 10^k+a_0\)，其中 \(a_s, a_{s-1}, \cdots , a_0\) 均小于 \(10^k\)。则 \(n\equiv a_0-a_1+a_2-a_3+\cdots +(-1)^s\cdot a_s\pmod m\)
经典余数定理
1. 剩余类
\(Z\) 按\(\bmod n\) 分为 \(0\pmod n, 1\pmod n,\cdots n-1\pmod n\)
\(Z_n=\lbrace\overline{0}, \overline{1},\cdots, \overline{n-1}\rbrace\)
2. 完全剩余系（简称完系）
\(x=\lbrace a_i\in\overline{i}\mid 0\le i\le n-1\rbrace\)
3. 欧拉 \(\varphi\) 函数
\(\varphi(n)\):\(0\sim n-1\) 与 \(n\) 互质的个数
\(m, n\) 互质 \(\Rightarrow\varphi(mn)=\varphi(m)\cdot\varphi(n)\)
4. 欧拉 \(\varphi\) 函数的计算
\(\varphi(n)=n\cdot \prod\limits_{i=1}^k(1-\frac{1}{p_i})\)
5. 既约剩余系（简称完系）
既约剩余系中的元素是剩余类中与 \(n\) 互质的元素。
6. 同余逆
已知 \((a, n)=1\)，则存在整数 \(b\) 使得 \(ab\equiv 1\pmod n\)，且这样的 \(b\) 在模 \(n\) 意义下是唯一的。则 \(b\) 称为 \(a\) 模 \(n\) 的同余逆，通常记作 \(a^{-1}\pmod n\)
7. 性质
若 \(\lbrace a_1, a_2, \cdots, a_n\rbrace\) 为模 \(n\) 的完系，则 \(\lbrace a_1+k, a_2+k, \cdots, a_n+k\rbrace\) 也为模 \(n\) 的完系
若 \(\lbrace a_1, a_2, \cdots, a_n\rbrace\) 为模 \(n\) 的完系，且 \((m, n)=1\)，则 \(\lbrace ma_1, ma_2, \cdots, ma_n\rbrace\) 也为模 \(n\) 的完系
若 \(\lbrace a_1, a_2, \cdots, a_{\varphi(n)}\rbrace\) 为模 \(n\) 的缩系，且 \((m, n)=1\)，则 \(\lbrace ma_1, ma_2, \cdots, ma_{\varphi(n)}\rbrace\) 也为模 \(n\) 的缩系
若 \(\lbrace a_1, a_2, \cdots, a_{\varphi(n)}\rbrace\) 为模 \(n\) 的缩系，则 \(\lbrace a_1^{-1}, a_2^{-1}, \cdots, a_{\varphi(n)}^{-1}\rbrace\) 也为模 \(n\) 的缩系
8. 中国剩余定理
已知 \(n_1,n_2\dots n_k\) 两两互质，同余方程组 \(\begin{cases}x\equiv a_1(\bmod n_1)\\[2ex]x\equiv a_2(\bmod n_2)\\[2ex]\cdots\\[2ex]x\equiv a_k(\bmod n_k)\\\end{cases}\) 在模 \(n=n_1n_2\dots n_k\) 的意义下有唯一解。
具体的，设 \(M_i=\dfrac{n}{n_i}\)，\(N_i^{-1}\) 表示 \(M_i\) 在模 \(n_i\) 意义下的逆元。该方程的解为 \(\sum\limits_{i=1}^{k} a_iM_iM_i^{-1}\)。
9. Wilson
如果 \(p\) 是一个素数，则 \((p-1)!\equiv p-1\pmod p\)
10. 费马小定理
\(p\) 为质数，\(a\) 不是 \(p\) 的倍数，则 \(a^{p-1}\equiv 1\pmod p\)
11. 欧拉定理
\(a\) 和 \(n\) 为正整数，且 \((a, n)=1\)，则 \(a^{\varphi(n)}\equiv 1\pmod n\)
12. 同余的重要式子
若 \(a^m\equiv 1\pmod n,a^k\equiv 1\pmod n\Rightarrow a^{(m, k)}\equiv 1\pmod n\)
13. 阶
若 \((a, n)=1\)，且存在最小的正整数 \(k\)，使得 \(a^k\equiv 1\pmod n\)，且 \(a^n\equiv 1\pmod n\Leftrightarrow k|n\)，此时的 \(k\) 叫做 \(a\) 模 \(n\) 的阶。
群论
1. 群的概念
群：集合 \(G\)，和运算 \(\ast\)，构成了一个群：\((G,\ast)\)。
群满足下面的性质：
运算封闭性： \(\forall x,y\in G,x\ast y\in G\)
单位元： \(\exists e\in G,\forall g\in G,e\ast g=g\ast e=g\)
逆元： \(\forall g\in G,\exists g'\in G,g\ast g'=g'\ast g=e\)，记作 \(g'=g^{-1}\)
结合律： \(\forall g_1,g_2,g_3\in G,(g_1\ast g_2)\ast g_3=g_1\ast(g_2\ast g_3)\) 。
可以证明单位元和逆元唯一。
逆元的性质： \((a\ast b)^{-1}=b^{-1}\ast a^{-1}\)
定义： \(a^b=\underbrace{a\ast a\ast a\cdots \ast a}_{b}\)
\(|G|\) 有限为有限群(如 \((\mathbb{Z_n,+}),({\{a_1,\cdots,a_{\varphi(n)}\},\times })\))， \(|G|\) 无限为无限群(如 \((\mathbb{Z},+)\))。
若 \(\forall a,b\in G,a\ast b=b\ast a\) 则称群 \((G,\ast)\) 为交换群（阿贝尔群）(如 \((\mathbb{Z},+)\))，否则称为非交换群(如 \((\mathbb{M_n},\times ),(\mathbb{S},\circ)\))。
若 \(H\subseteq G,(H,\ast )\) 也是群，则称 \((H,\ast )\) 为 \((G,\ast)\) 的子群（如 \((\mathbb{Z},+)\) 的子群为 \((n\mathbb{Z},+),n\in\mathbb{Z}\) ）。
循环群：若 \((G,\ast),G=\{a^m|m\in \mathbb{Z}\}\) 则称 \((G,\ast)\) 为循环群。记作 \((G,\ast)=<a>\)，\(a\) 为群 \((G,\ast)\) 的生成元，循环群一定是交换群（如 \((\mathbb{Z},+)=<1>\) ）。
同构： 存在双射 \(f:(G_1,\ast_1)\to (G_2,\ast_2)\) ,使得 \(\forall g_1,g_2\in G_1,f(g_1)\ast_2f(g_2)=f(g_1\ast_1 g_2)\)，则称 \((G_1,\ast_1)\) 和 \((G_2,\ast_2)\) 同构，记作 \((G_1,\ast_1)\cong (G_2,\ast_2)\) 。
若两个循环群元素个数相同，则两个循环群同构，所以任意一个 \(n\) 个元素的循环群同构 \((\mathbb{Z_n},+)\),任意一个无限循环群同构 \((\mathbb{Z},+)\)。
任意一个 \(n\) 个元素的循环群有 \(\varphi(n)\) 个生成元。
任意一个非交换群都同构 \((\mathbb{S},\circ)\)
若 \((H_1,\ast),(H_2,\ast)\) 均为 \((G,\ast)\) 的子群，则 \((H_1\cap H_2,\ast)\) 为 \((G,\ast)\) 的子群
拉格朗日定理： 若 \((H,\ast)\) 为 \((G,\ast)\) 的子群，则 \(|H|\Big\vert |G|\) 。
2. 阶
阶：最小的 \(k\in \mathbb{N^{\ast}}\) 使得 \(g^k=e\)，则称 \(k\) 为 \(g\) 在群 \((G,\ast)\) 的阶，记作 \(o(g)\)。
在 \((\mathbb{Z},+)\) 中，对于 \(g\ne 0,o(g)=+\infty\)
在 \((G,\ast)\) 中，\(o(e)=1\)
在交换群 \((G,\ast)\) 中，若 \(o(g)=n,o(g^k)=\dfrac{n}{\gcd(n,k)}\)
在交换群 \((G,\ast)\) 中，\(\max\{o(g)|g\in G\}=\mathrm{lcm}\{o(g)|g\in G\}\)
在交换群 \((G,\ast)\) 中，\(g_1,g_2\in G\),若 \(\gcd(o(g_1),o(g_2))=1,o(g_1\ast g_2)=o(g_1)o(g_2)\)
3. 置换群
定义置换 \(S_n\) 为双射 \(f:\{1\sim n\}\to \{1\sim n\}\) 。记作 \(\begin{pmatrix}1,2,\cdots n\\ a_1,a_2\cdots a_n\end{pmatrix}\) 表示 \(f(i)=a_i\) 。
轮换：\((i_1,i_2,\cdots i_n)\) 为 \(f(i_j)=\begin{cases}i_{j+1}(j\ne n)\\i_1(j=n)\end{cases}\) 。
\(\forall \alpha \in S_n\) \(\alpha\) 可以分解成若干个不相交轮换的乘积。
不相交轮换的乘积具有交换律。
若将 \(\alpha\in S\) 分解成若干个不相交轮换的乘积，即 \(\alpha=S_1\circ S_2\cdots S_k\) ，则 \(o(\alpha)=\mathrm{lcm}(|S_i|(1\le i\le k))\)