数论初步内容，主要是线性代数与组合（可能有点杂，因为我不知道放哪）。
同余
同余的性质
直接看成没有除法的加法就可以了，没关系的。
解同余方程
使用 Exgcd 可以解同余方程 。
解同余方程组
使用 Exgcd 解每一个方程，然后取所有解的 lcm 就是答案。
这就是 ExCRT。
乘法逆元
但如果我们想要做除法怎么办：使用费马小定理即可。
费马小定理：$a^{-1}=a^{p-2} \pmod p$。要求 $p$ 为质数。
你说 $p$ 不为质数怎么办？如果题目保证一定存在逆元，则使用 Exgcd 求解出的 $x$ 就是逆元。
如果不保证？说明出题人……，不想让你做除法。
其他
应该考不到。
组合
请选择你的阵营：
- 组合意义天地灭，代数推导保平安
- 代数推导天地灭，组合意义保平安
目前不会代数推导，数学太差了呜呜呜。
组合基础
有以下记号：
- $C_{n}^{m}$ 或者 $(^n_m)$ 表示从 $n$ 个元素中选出 $m$ 个元素的方案数。个人更喜欢 $C$ 的写法。
- $A^m_n$ 表示从 $n$ 个元素中选出 $m$ 个的排列数。
$C$ 是无序的，$A$ 是有序的，也可以认为 $C$ 选出了一个集合，$A$ 选出了一个序列。
$A^m_n=\dfrac{n!}{(n-m)!}$
$C_n^m=\dfrac{n!}{m!(n-m)!}$
虽然这个式子已经很优雅了，但不是人类能够计算的，所以我们手玩时可以用这个：
$A_n^m=n\times (n-1)\times …\times (n-m+1)$
$C_n^m=\dfrac{n\times (n-1)\times …\times (n-m+1)}{m\times (m-1)\times ……1}$
这两个式子也同时方便了我们 $n,m$ 不同阶时暴力计算组合/排列数。
多重集的排列数（多重组合数）
这里指包含重复元素的广义集合，比如集合 $S={n_1\times a_1,n_2\times a_2,…,n_k\times a_k}$
所以 $S$ 的全排列个数为：$\dfrac{n!}{n_1!n_2!…n_k!}$
或用符号表示为：$\dbinom{n}{n_1,n_2,…,n_k}$
亿点点公式
我坚定选择组合意义！代数推导太暴力，不够优雅。
$\dbinom{n}{m}=\dbinom{n}{n-m}$ 或 $C_n^m=C_n^{n-m}$
正确性显然，你选完 $m$ 个剩下的 $n-m$ 个也是选好的。
$\dbinom{n}{k}=\dfrac{n}{k}\dbinom{n-1}{k-1}$
可以理解为，先在 $n-1$ 中选出 $k-1$ 个，然后再选最后一个。每一个元素都可能成为最后一个，所以 $\times n$，但这样会算重，一个元素会被贡献 $k$ 次，所以 $\div k$ 。
$\dbinom{n}{m}=\dbinom{n-1}{m-1}+\dbinom{n-1}{m}$
可以理解为 $n-1$ 选 $m-1$ 个，然后第 $n$ 个必选 加上 $n-1$ 选 $m$ 个，第 $n$ 个不选的方案数。
上述用代数推导直接暴力展开就行了。
$\sum_{i=0}^{n}\dbinom{n}{i}=2^n$
从 $n$ 个数中，不选，选 $1$ 个，选 $2$ 个……选 $n$ 个。这不就是 状压dp 的形式，直接 $2^n$ 就行。
$\sum_{i=0}^{n}(-1)^i \dbinom{n}{i}=[n=0]$
容斥原理，还是考虑是 状压dp 的形式，所有数都会被抵消。
$\sum_{i=0}^{k}\dbinom{n}{i}\dbinom{m}{k-i}=\dbinom{m+n}{k}$
范德蒙德卷积，很高级，所以我不会。将一个大集合划分成两个小集合，然后在两个小集合中分别选。
$\sum_{i=0}^{n}\dbinom{n}{i}^2=\dbinom{2n}{n}$
不会的请下载国家反诈APP
$\sum_{i=0}^{n}i\dbinom{n}{i}=n2^{n-1}$
这个咱代数推导吧，我真编不下去了。给它全展了，然后合一合就行了。（好像是，也有可能是我推错了）
$\sum_{l=0}^{n}\dbinom{l}{k}=\dbinom{n+1}{k+1}$
不会，太难了，编不下去了。
$\dbinom{n}{r}\dbinom{r}{k}=\dbinom{n}{k}\dbinom{n-k}{r-k}$
从 $n$ 中先选 $r$ 个，再从 $r$ 中选 $k$ 个的方案数，等同于先从 $n$ 中选 $k$ 个，再从剩余地方选 $r-k$ 个。
二项式反演
若：$g_i=\sum_{j=0}^{i}\dbinom{i}{j}f_j$
则：$f_i=\sum_{j=0}^{i}\dbinom{i}{j}(-1)^{i-j}g_j$
这个是原式，显然没用。
变式：
- 若：$g_i=\sum_{j=i}^{n}\dbinom{j}{i}f_j$
- 则：$f_i=\sum_{j=i}^{n}\dbinom{j}{i}(-1)^{j-i}g_j$
$f_i$ 表示“恰好 i 个”，$g_i$ 表示“钦定 i 个”。
不会推导，不会做题，全剧终。
线性代数
矩阵运算
矩阵运算有加法和乘法两种。
只有长得完全一样的矩阵能相加，只有矩阵 A 的宽等于矩阵 B 的高的矩阵才能相乘。
矩阵的运算具体可以看 OiWiki，Latex 已经敲傻了。
具体运用是矩阵快速幂以及线段树维护矩阵。
矩阵快速幂用来加速递推，因为转移矩阵是相同的，而矩阵乘法有结合律。
线段树维护矩阵可以方便的维护大量信息，同样因为矩阵乘法有结合律，所以属于半群信息。
高斯消元
将高斯消元看作矩阵，一直做恒等变换就是在消元。
建议直接学校 高斯-约旦 消元。
代码短且简介，符合人类思考过程。
线性基
对于一堆数的异或值，支持以下：
- 查询某个值是否能被异或出来，是否存在。
- 任选数异或的最大/最小值。
- 查询任选数异或的第 k 大值。
非常强力，但是不会。