Bunny Jump——斐波那契数列

序

斐波那契数列是一个很有意思的东西，它的每一项都由前两项的和导出，即对于 ，有 。入门算法时，尤其是刚开始涉及递归函数时，你可能就已经写过求解斐波那契数列通项的函数了。基于递归的算法会将当前数分为两个较小的数，然后继续分解直到变为 。一般来说，这样的算法复杂度是 的，极其不友好。我们会选择从定义出发，也就是使用循环结构来递推。等到了提高组，你会发现这个算法也不是最优的，稍微了解线性代数（此处尤指矩阵乘法）后，你会发现斐波那契数列的通项可以由下面这个矩阵递推式给出：

如果你熟悉数学，尤其是对生成函数有一定了解，那么你一定知道下面这个关于斐波那契数列的生成函数：

生成函数作用可大，能够快速求出数列对应项的系数。经典的“换硬币问题”就可以使用生成函数快速求解。对生成函数进行一番操作后，你会得出它的通项公式：

在计算机中会涉及到精度问题，因此我们一般使用复杂度为 的矩阵快速幂做法。接下来我们将对斐波那契数列进行一个深入的信息学方面的探究。

齐肯多夫表示法

众所周知，二进制是一种计数系统，即用 0/1 表示所有的数。那么对于斐波那契数列里的数，是否也有这样的优美性质呢？答案是肯定的，齐肯多夫证明了所有的数都可以被分解成若干斐波那契数的和，例如 。拆分方法跟二进制分解相同，找到小于等于目标数的第一个斐波那契数，并减去，重复该过程直到被分解完毕。

与二进制一样，我们也用一个 01 串来表示分解的结果。第 位对应着分解出的和式中包含 项，因此上例可以表示成：。

CF 126D - Fibonacci Sums

题目地址：CF 126D

题目难度：省选/NOI-

计算一个整数被分解成若干个各不相等的Fibonacci数列中的数的方案。

根据齐肯多夫表示法的定义，解出的 01 串按理来说是不应该含有连续的 1 的，因为连续的 1 可以累加成下一个斐波那契数。既然题目都说了，那我们其实可以反过来利用这个结论。也就是求出标准齐肯多夫表示（不含连续的 1）后对每个 100* 模式串（1 后面至少跟两个 0）进行拆解变为 011*，如果后面还有零，例如 011000 可以继续拆成 010110，以此类推……

因此设计状态转移方程为 ，表示是否拆分第 位的 1，并令 表示标准拆分的第 位有一个 1。

考虑答案从何而来。如果不拆当前位，那我们可以对它的子序列 进行拆分（或者同样不拆分子序列），答案就由子序列贡献得到，即 。

如果要拆分当前这一位，同样也和它的子序列有关。不过， 和 之间如果相隔大于等于两个 0，也就是 时，就可以进行拆分（即 100* 拆分为 011*）。拆分后如果剩余空位大于等于 那么就还可以继续拆分，但是此时只能对最末尾的 1 进行拆分了，因为经历若干轮拆分后的序列一定形如 10101010*。问题转化成最多能在空位里留下多少个互不相邻的 1（包括端点的 1），答案即为 。如果钦定了下一位也不拆分，那么答案就是 。综上所述：

需要注意的是，此时我们会将斐波那契数列整体左移一位变为 ，因此分解式中 1 位的位置也要顺带移动一位。