数学题单 Part I

按照知识点排序，顺序和难度没有必然联系。 还有些非洛谷题目会在这里呈现。 ### 快速幂 一切拥有**结合律**的代数结构都可以定义幂运算（这里不含多项式快速幂）。 对于矩阵快速幂，可以在 $\Theta(n^3\log V)$ 的时间内求出常系数齐次线性递推数列的某一项，其中 $V$ 是值域，$n$ 是特征方程的次数。（我们还会在多项式的地方见到线性递推。） 对于转移满足一定形式的 dp，我们可以考虑利用矩阵快速幂优化转移。 对于**底数固定**的模意义下的快速幂，我们可以通过 $\Theta(\sqrt p)$ 预处理来实现 $\Theta(1)$ 查询，简称“光速幂”。 - [P1226 【模板】快速幂](https://www.luogu.com.cn/problem/P1226) / [P3390 【模板】矩阵幂](https://www.luogu.com.cn/problem/P3390) 板子。 - [P1962 斐波那契数列](https://www.luogu.com.cn/problem/P1962) / [P1306 广义斐波那契数列](https://www.luogu.com.cn/problem/P1306) / [P2044 [NOI2012] 随机数生成器](https://www.luogu.com.cn/problem/P2044) 常系数齐次线性递推的矩阵快速幂优化。 - [P3758 [TJOI2017] 可乐](https://www.luogu.com.cn/problem/P3758) / [P5789 [TJOI2017] 可乐（加强版）](https://www.luogu.com.cn/problem/P5789) 矩阵快速幂优化 dp。 - [P5175 数列](https://www.luogu.com.cn/problem/P5175) 稍微有一点意思的**常系数**齐次线性递推，由于 IO 量过大**可能需要快速快写**。 - [P4967 黑暗打击](https://www.luogu.com.cn/problem/P4967) TODO。 - [LOJ #162. 快速幂 2](https://loj.ac/p/162) $\Theta(\sqrt p)-\Theta(1)$ 固定底数快速幂（光速幂）。 - [P5110 块速递推](https://www.luogu.com.cn/problem/P5110) 特征方程，光速幂。 - [P5303 [GXOI/GZOI2019] 逼死强迫症](https://www.luogu.com.cn/problem/P5303) 矩阵快速幂。 - [P3746 [六省联考 2017] 组合数问题](https://www.luogu.com.cn/problem/P3746) 矩阵快速幂 / 多项式在循环卷积意义下的快速幂（可以暴力做）。 - [P3263 [JLOI2015] 有意义的字符串](https://www.luogu.com.cn/problem/P3263) / [P5136 sequence](https://www.luogu.com.cn/problem/P5136) 矩阵快速幂 + Vieta 定理。