从斐波那契数列说起

从前有一只求知若渴的兔子，ta来自一个神奇的不亡兔家族：

他们的祖先亚当兔和夏娃兔（雄兔和雌兔），每个月都会生下一雄一雌两只兔，每对小兔子都要花一个月长大，长大后也继承了祖辈的优良基因，再过一个月，每对兔子每个月都会生下一雄一雌两只兔。

这些兔子受到了永生的祝福抑或是诅咒。子子孙孙无穷匮也，造成了极大的生态破坏。于是，这只智慧的小兔几就想通过自己的努力学习，来修复一些损失。

兔子问题的建模如下，设第个月有 对兔子：

对不起高树老师和小火炉老师，全还给老师了。现在翻到离散数学第206页（第十二章 递推函数与生成函数），让我们一起温新而知新。

数学复习

递推方程的定义

复习高等数学/离散数学中的概念：

递推方程：给定数的序列 ，把 与一些 联系起来的等式

初值：（字面意思，初值是初值）

常系数线性齐次递推方程：

其中 , 是常数，

该递推方程的特征方程：

方程的特征根：它的 个根

斐波那契数列问题的求解

斐波那契数列的递推方程

使用书上的例题

时，得到常系数线性齐次递推方程：

该递推方程的特征方程:

解一元二次方程：

代入 ,得

矩阵形式：

高斯消元法解矩阵方程，增广矩阵为：

得：

从这个结果中可以发现，在实际的计算中， 的初值更方便运算，这样公式直接变成 就好了。计算过程是一样的。

斐波那契数列的快速幂矩阵算法

数学证明

为了方便计算，重新定义一下初值

状态向量

构造状态向量：

则前一状态为：

将递推关系用矩阵表示：

因此：

的意思是按定义等于

转移矩阵

其中转移矩阵：

反复应用递推：

而初始向量：

故：

要求 ，有两种主要方法

观察法 + 数学归纳法

先观察 的规律，

可以猜想：

通过归纳法可证：

当 时，

假设对 成立，即

则

结论成立,即

结论

设转移矩阵：

则

即 是 右上角或者左下角的数值

快速幂算法

关于 ，常常使用快速幂算法。时间复杂度为 。

该算法通过不断将指数右移（相当于除以2），并根据当前指数的奇偶性决定是否将当前的乘到结果中。

Python 自带快速幂算法，比自己实现的快

pow(a,b,p)

自己实现C++代码：

using ll = long long;
using namespace std;
ll quick_pow(ll a, ll b, ll p)
{
    ll ret = 1; // 零次方为 1
    while (b) //指数还没除完
    {
        if (b & 1) // 指数是奇数
            ret = ret * a % p; //乘上当前底数
        a = a * a % p; // 奖池平方累计
        b >>= 1; //指数除以2
    }
    return ret;
}

快速幂矩阵算法

同样采用快速幂算法的思想。
（此模块施工中）

编程例题：“斐波那契数列”

https://www.luogu.com.cn/problem/P12847

题目描述

斐波那契数列是一个满足如下要求的数列

我们规定一个类似的数列满足

求该数列 的前 项的乘积对 取模的结果。

输入格式

输入一行包含一个正整数 。

输出格式

输出一行包含一个整数表示答案。

输入输出样例 #1

输入 #1

5

输出 #1

69984

说明/提示

【评测用例规模与约定】

对于 70% 的评测用例，；

对于所有评测用例，。

解题

已知

设

则

由此找规律：

设斐波那契数列

即当 时

由于评测用例可能高达 ，完整的求解一定要优化

通过解常系数线性齐次递推方程可得 ，然而这个方法会造成很大的精度误差，而编程环境不一定有高精度库，所以要用“整数方法”。

总结

1. 通过特征方程，可以求解递推方程的表达式
2. 矩阵方程的解法有增广矩阵法和逆矩阵法