整理了一些fib数列相关的经典问题和trick.
,这被称为卡西尼恒等式.
一个非常简单的证明来自那个矩阵快速幂做法.或许你可以认为它就是这么来的.
两边取行列式就得到上面的恒等式.如果你观察过\(11\)-fib数的转移矩阵自己快速幂的结果,你可能也会发现这个.如果你真的很无聊,对它两边取det,你就独立发现了卡西尼恒等式.
你可以在具体数学上看到这个.这个东西居然真的有用/jy,一会我们真的会用到它.
循环节和初值往往没有很密切的关系.
证明 感谢洛谷用户 @论文 和我校mo爷Fanzor的指导.
fib数比起广义fib数,膜任意数下循环节都很小,这是因为它的\(a^2+4b\)非常小,以至于特殊情况非常少.
下面是一些例题.
有经典题如下.
刚才我们做了两个值的问题,可是这里只有一个值啊?
一个常数优化是,注意到\(f_0f_1\)是不变的,它那边只需要跑一遍,另一边跑四遍,这样就从八遍枚举变成了五遍枚举.