中科大2024强基数学压轴题的算法解析

发表于 分类于

最近，中科大2024年强基数学考试的压轴题引起了广泛关注。题目如下：

有数列Fn=Fn−1+Fn−2,F1=1,F2=1,求F1958的个位数\text{有数列}F_n = F_{n-1}+F_{n-2}, F_1 = 1, F_2 = 1, \text{求}F_{1958}\text{的个位数}

这个数列是著名的斐波那契数列，对此类多项递推问题，我们可以采用改写矩阵形式的方法解决。

斐波那契数列的矩阵递推形式

我们可以将斐波那契数列的递推式写成矩阵形式：

(Fn+1Fn)=(1110)(FnFn−1)\begin{pmatrix} F_{n+1} \\ F_n \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix}

这就是一个典型的乘积递推问题，显然我们可以找到其通项公式：

(FnFn−1)=(1110)n−2(F2F1)\begin{pmatrix} F_{n} \\ F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n-2} \begin{pmatrix} F_2 \\ F_1 \end{pmatrix}

变换可知：

Fn=∣(10)(FnFn−1)∣=∣(10)(1110)n−2(11)∣F_{n} = | \begin{pmatrix} 1 & 0 \end{pmatrix} \begin{pmatrix} F_{n} \\ F_{n-1} \end{pmatrix} | = |\begin{pmatrix} 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n-2} \begin{pmatrix} 1 \\ 1 \end{pmatrix} |

至此我们可以用矩阵快速幂求解。

对模10意义下的性质解析

由于此题为笔试题，直接手算矩阵快速幂显然是不优雅的，在进行矩阵快速幂的同时，我们可以对模10意义下的性质进行分析。

不难发现，矩阵(1110)\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}的222^2次方等于其262^6次方。

那么该矩阵模1010意义下的nn次幂存在周期TT，且T≤60T\leq 60。

此时我们就可以对n−2n-2取模以简化运算。

方阵幂算法

对于此类多项递推问题，我们还可以通过方阵幂算法求解其通项公式。

方阵幂算法的核心是对矩阵通过矩阵的特征值进行对角化，然后通过对角化矩阵的幂求解原矩阵的幂。

该数列的递推矩阵即可对角化过程如下：

求解其特征值：

∣1−λ11−λ∣=0 \begin{vmatrix} 1-\lambda & 1 \\ 1 & -\lambda \end{vmatrix} = 0

解得λ=1±52\lambda = \frac{1\pm\sqrt{5}}{2}，对应特征向量为(1+521)\begin{pmatrix} \frac{1+\sqrt{5}}{2} \\ 1 \end{pmatrix}和(1−521)\begin{pmatrix} \frac{1-\sqrt{5}}{2} \\ 1 \end{pmatrix}。

那么我们可以得到：

(1110)=(1+521−5211)((1+52)00(1−52))(1+521−5211)−1\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} \frac{1+\sqrt{5}}{2} & \frac{1-\sqrt{5}}{2} \\ 1 & 1 \end{pmatrix} \begin{pmatrix} \left(\frac{1+\sqrt{5}}{2}\right) & 0 \\ 0 & \left(\frac{1-\sqrt{5}}{2}\right) \end{pmatrix} \begin{pmatrix} \frac{1+\sqrt{5}}{2} & \frac{1-\sqrt{5}}{2} \\ 1 & 1 \end{pmatrix}^{-1}

此时利用矩阵对角化的特性：

(1110)n−1=(1+521−5211)((1+52)n−100(1−52)n−1)(1+521−5211)−1\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^{n-1} = \begin{pmatrix} \frac{1+\sqrt{5}}{2} & \frac{1-\sqrt{5}}{2} \\ 1 & 1 \end{pmatrix} \begin{pmatrix} \left(\frac{1+\sqrt{5}}{2}\right)^{n-1} & 0 \\ 0 & \left(\frac{1-\sqrt{5}}{2}\right)^{n-1} \end{pmatrix} \begin{pmatrix} \frac{1+\sqrt{5}}{2} & \frac{1-\sqrt{5}}{2} \\ 1 & 1 \end{pmatrix}^{-1}

至此我们可以将以上结果代入矩阵形式通项公式得到结果。