洛谷秋令营Day7-数学

数论

唯一分解定理、gcd、exgcd、费马小定理、批量快速素因数分解、CRT，提高组不考扩展 CRT，但裸的 CRT 考出来又只是一个板子题，所以提高组主要考 gcd 相关的题目。

P9473，其实就是考虑每种素因子的最小次数和最大次数。

组合

杨辉三角、卡特兰数也得会。

二项式定理的逆用，从而把一个 $O(n)$ 的计算换成一个 $O(1)$ 或 $O(\log n)$ 的计算。

$C(n, i) \times 2^i$，可以凑一个 $1^{n-i}$，从而就是 $(2+1)^n = 3^n$，从枚举 $i$ 变成只需要快速幂就好了。

P8106，枚举 S 的大小，直接算就好了，需要特判 S 和 T 一样大的情况。

gym106072D，从大到小删，并且考虑每个数的贡献时，只关心比这个数小的数有多少个，所以只需要排序后，枚举每个数，看比自己大的数随便选，比自己小的数选若干个会贡献多少就好了。

P5481，模数不一定是素数，不能求逆元，先求出一行的方案，再取 n 个排列就好了。具体算的时候是羊神最喜欢的那个球盒问题的计算。

代数

包括矩阵乘法，矩阵快速幂，高斯消元，其实内容很少。

P1939，构造矩阵跑矩阵快速幂转移就好了。如何构造？待定系数法。

P10499，高斯消元，求解异或方程组，主要是建模，我们考虑对于第 $i$ 个开关，主动按哪些开关时会让这个开关的状态也变化。这样的话，假如我们知道每个开关到底按没按，只需要把这两个东西做一个对应位置的与操作，再把与的结果异或起来（类似内积先乘后加），就是最终经过这些操作后到底改没改变这个开关的状态了。解的个数其实就是看有多少个全为 0 的行，是否无解主要看全为 0 的行的右边是否非 0。