

数列

Copyright

本页面斐波那契数列部分转载于数列-OI Wiki。本页面贡献者：LyuLumos。本页面内容遵循 MIT 协议，转载请附上原文出处链接和本声明。

斐波那契数列¶

定义¶

斐波那契数列（The Fibonacci sequence）的定义如下：

$F_0 = 0, F_1 = 1, F_n = F_{n-1} + F_{n-2}$

该数列的前几项如下：

$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...$

性质¶

斐波那契数列拥有许多有趣的性质，这里列举出一部分简单的性质：

卡西尼性质： $F_{n-1} F_{n+1} - F_n^2 = (-1)^n$ 。
附加性质： $F_{n+k} = F_k F_{n+1} + F_{k-1} F_n$ 。
取上一条性质中 $k = n$ ，我们得到 $F_{2n} = F_n (F_{n+1} + F_{n-1})$ 。
由上一条性质可以归纳证明， $\forall k\in \mathbb{N},F_n|F_{nk}$ 。
上述性质可逆，即 $\forall F_a|F_b,a|b$ 。
GCD 性质： $(F_m, F_n) = F_{(m, n)}$ 。
以斐波那契数列相邻两项作为输入会使欧几里德算法达到最坏复杂度。
齐肯多夫定理：任何自然数 $n$ 可以被唯一地表示成一些互不相邻斐波那契数的和。

斐波那契数列通项公式¶

第 $n$ 个斐波那契数可以在 $\Theta (n)$ 的时间内使用递推公式计算。但我们仍有更快速的方法计算。

解析解¶

$F_n = \frac{\left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n}{\sqrt{5}}$

这公式在计算的时侯要求极高的精确度，因此在实践中很少用到。但是请不要忽视！结合模意义下二次剩余和逆元的概念，在一些情况中使用这个公式仍是有用的。

矩阵形式¶

斐波那契数列的递推可以用矩阵乘法的形式表达：

$\begin{bmatrix}F_{n-1} & F_{n} \cr\end{bmatrix} = \begin{bmatrix}F_{n-2} & F_{n-1} \cr\end{bmatrix} \cdot \begin{bmatrix}0 & 1 \cr 1 & 1 \cr\end{bmatrix}$

设 $P = \begin{bmatrix}0 & 1 \cr 1 & 1 \cr\end{bmatrix}$ ，我们得到

$\begin{bmatrix}F_n & F_{n+1} \cr\end{bmatrix} = \begin{bmatrix}F_0 & F_1 \cr\end{bmatrix} \cdot P^n$

于是我们可以用矩阵快速幂在 $\Theta(\log n)$ 的时间内计算斐波那契数列。

思考¶

那广义斐波那契数列（满足通项公式但是数值不同）呢？

卡特兰数列¶

定义¶

Catalan数定义如下：

$f_0=1,\,\,f_n = \sum_{i=0}^{n-1}f(i)\cdot f(n-i-1), n \in N_+$

该数列的前几项如下：

$1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012 ......$

递推公式¶

$f(n) = \frac{1}{n+1}\tbinom{2n}{n}$
$f(n) = \tbinom{2n}{n}-\tbinom{2n}{n-1}$ // 推荐
$f(n) = \sum_{i=0}^{n-1}f(i)×f(n-i-1)$
$f(n) = \frac{f(n-1)×(4n-2)}{n+1}$

应用¶

二叉树的计数问题：已知二叉树有 $n$ 个结点，求能构成多少种不同的二叉树。
括号化问题：一个合法的表达式由()包围，()可以嵌套和连接，如：(())()也是合法表达式，现给出 $n$ 对括号，求可以组成的合法表达式的个数。
划分问题：将一个凸 $n+2$ 多边形区域分成三角形区域的方法数。
出栈问题：一个栈的进栈序列为 $1,2,3,..n$ ，求不同的出栈序列有多少种。
路径问题：在 $n\cdot n$ 的方格地图中，从一个角到另外一个角，求不跨越对角线的路径数有多少种。
握手问题： $2n$ 个人均匀坐在一个圆桌边上，某个时刻所有人同时与另一个人握手，要求手之间不能交叉，求共有多少种握手方法。

例题¶

宗老师的影响力（2020牛客寒假算法基础集训营1-J 2300）

zls在众人齐心协力下，影响力越来越大了！

已知第一天影响力为 $x$ ，第二天影响力为 $y$ ，从第三天开始，每一天的影响力为前两天影响力的乘积再乘以 $a$ 的 $b$ 次方。用数学语言描述是：设第 $i$ 天的影响力为 $f(i)$ ，那么 $f(1)=x$ ， $f(2)=y$ ，对于 $i>2$ ， $f(i)=f(i-1)\cdot f(i-2)\cdot a^b$ 。

我们想知道zls第 $n$ 天影响力是多少？（ $1\leq n,a,b,x,y\leq 10^{12}$ ）

因为zls的影响力实在是太大了，所以只需要输出其对 1000000007 模的值就可以了。

解题思路

显然有 $f(n)=x^{F_{n-2}}y^{F_{n-1}}a^{(F_{n-1}-1)b}$

矩阵快速幂+快速幂+费马小定理求逆元解决