#14. 我真的不会高中数学（上）

· · 算法·理论

还会有（中）和（下），但是要准备 NOI，并且 NOI 不考，所以可能得等到高三了。

在阅读本文前，你可能需要一定的数学基础。

定义 常系数齐次线性递推数列

对于无限序列 \{a_n\} 和有限序列 \{r_m\}，其中 r_0=0，若对于任意 n\ge m，都有 a_n=\sum\limits_{i=1}^{m}r_ia_{n-i}，则称 \{a_n\} 是常系数齐次线性递推数列。

Q1. 如何判定一个数列是否是线性递推？

一个简单的方法是利用 Generating Function，设 A(z) 是数列 \{a_n\} 的生成函数，若存在两个有限多项式 S,R 满足 A=\frac{S}{R} 且 R 的常数项为 1。

还有一种方法是通过矩阵乘法来理解递推，对于一个 n\times n 的矩阵 M，无限数列 \{I,M,M^2,M^3\dots\} 是一个线性递推数列，它的最短线性递推式阶数不超过 n。

Q2. 如何求给定线性递推数列的最短递推式？

最简单的方法是使用高斯消元法，可以在 O(m^3) 的复杂度内求出递推式。下面会介绍一个更厉害的在 O(m^2) 求解线性递推的算法。

算法 Berlekamp Massey

这里本来有一个介绍，但是它丢了。

Q3. 如何求某一项？

注意，这里不是求通项。但是需要 114514 级算法，所以不讲。

Q4. 如何求通项？

一个常见的例子是斐波那契数列 f_{n}=f_{n-1}+f_{n-2}，而一个常见的做法是求特征方程。

这里不妨直接给出特征方程：C(x)=x^m-\sum_{i=1}^{m}r_ix^{m-i}=0。我们还是从生成函数的角度来思考，将 x 代换成 F(x)，令 R(x)=\sum_{i=1}^{m}r_ix^{i}+1，有 R(x)=x^{m}C(\frac{1}{x})。可以将 F(x) 写成 \frac{P(x)}{R(x)} 的形式，

草了有点困难，反正根据结论，分母可以写成 \prod (1-\lambda_i)^k_i 这种形式。当 \lambda_i 互不相同且 k_i=1 时特征多项式五重根，可以写成 \sum \frac{c_1}{1-\lambda_i} 的形式，也就是 a_n=\sum c_i\lambda_i^n。

这是推导出特征多项式的方向，接下来考虑直接证明结论：

显然 a_n=\lambda_i^n 是一组特解，应是解空间的一个基底。于是当 \lambda_i\ne \lambda_j 的时候解应该是 \lambda_i^n 的线性组合。这个组合是唯一的，这可以通过矩阵行列式不为 0 得到。

当然这个系数矩阵行列式就是范德蒙德行列式，不为 0 的充要条件是 \lambda_i\ne \lambda_j。

对于有重根的部分，假设某个根重复了 m_i 次，则 a_n=\sum_{i=1}^{t}(\sum_{j=0}^{m_i-1} \alpha_{i,j}n^j)\lambda_i^n。

证明留作作业（只用考虑 n^j\lambda^{n} 是不是一个通解）。

对于根不是实数情况不清楚，互不相同的结论应该还是对的。

Q5. 怎么写代码？

由于高次方程不好处理，这里只考虑二阶递推。问题在于 \sqrt{\Delta} 可能不存在二次剩余。考虑扩域为 \mathbb{F}_w 即设 w=\sqrt{\Delta}，将所有数表示成 a+bw，由于剩下的部分都是有理数，所以不存在冲突。

由于最后的解 a_n 一定是一个有理数，所以直接大力计算即可，最后“虚部”一定是 0。

另一个 OI 里扩域的例子是 Cipolla 算法。

算法 Cipolla

求解二次剩余 x^2\equiv a\pmod p 的解。根据欧拉准则，a^{\frac{p-1}{2}}\equiv 1\pmod p 时有解。

引理 a^p+b^p\equiv (a+b)^p\pmod p。证明二项式定理展开即可。

考虑构造一个数 x^2-a\equiv 0，而我们知道 x^2\equiv x^{p+1} 就有 x\equiv x^{\frac{p+1}{2}}\equiv \sqrt{a}。利用引理，希望找到 (x+y)^{\frac{p+1}{2}}，因为这玩意的平方就是 x^2+y^2，如果 y=\sqrt{a},x=0 就好了，不妨变成 x=n,y=\sqrt{a-n^2}。只要保证 a-n^2 没有二次剩余，就可以扩域了。只需证明加减乘除是封闭的即可，分类讨论一下显然。

这个算法目前是有问题，原因是费马小定理在 \mathbb{F}_w 下不成立。考虑修正一下有 w^{p}=-w，于是令 w=\sqrt{n^2-a} 即可。