斐波纳契数的总和？ [关闭]

Question

如何找到这个系列的总和

fib(0)^K + fib(C)^K + fib(2*C)^K + fib(3*C)^K + ... + fib(N*C)^K

约束是0 < N < 10^15，0 < C < 11和0 < k < 11？

这里fib(i)是第i个斐波纳契数，其中fib(0)=0，fib(1)=1和fib(n) = fib(n-1)+fib(n-2)。我们必须计算模数为1000000007（10 ^ 9 + 7）的总和。

Answer 1

这基本上是一种操纵复发关系的练习。要理解这个答案，您应该在矩阵和系统表单之间切换。

首先，我们得到了fib(i)^K的复发。这实际上涉及fib(i)^K, fib(i)^(K-1) fib(i-1), fib(i)^(K-2) fib(i-1)^2, ..., fib(i-1)^K的复发系统。我将为K = 3演示。

fib(i)^3 = (fib(i-1) + fib(i-2))^3
         = fib(i-1)^3 + 3 fib(i-1)^2 fib(i-2) + 3 fib(i-1) fib(i-2)^2 + fib(i-2)^3
fib(i)^2 fib(i-1) = (fib(i-1) + fib(i-2))^2 fib(i-1)
                  = fib(i-1)^3 + 2 fib(i-1)^2 fib(i-2) + fib(i-1) fib(i-2)^2
fib(i) fib(i-1)^2 = (fib(i-1) + fib(i-2)) fib(i-1)^2
                  = fib(i-1)^3 + fib(i-1)^2 fib(i-2)
fib(i-1)^3 = fib(i-1)^3

这些可以组合成单个矩阵。

[fib(i)^3    fib(i)^2 fib(i-1)    fib(i) fib(i-1)^2    fib(i-1)^3] =
                                                                           i
= [fib(0)^3    fib(0)^2 fib(-1)    fib(0) fib(-1)^2    fib(-1)^3] [1 0 0 0]
                                                                  [3 1 0 0]
                                                                  [3 2 1 0]
                                                                  [1 1 1 1]
                     i
= [0 0 0 1] [1 0 0 0]
            [3 1 0 0]
            [3 2 1 0]
            [1 1 1 1]

你可能会认出Pascal的三角形。

现在，给定函数f(i)的递归系统，我们可以通过将矩阵提升到幂f(c i)来计算c的重现。

最后一步是从f(i)的复发到F(i) = f(0) + f(1) + ... + f(i-1)的复发。添加方程式很简单

F(i) = F(i-1) + f(i-1)

到系统。

计算了矩阵，我估计最多只有12^2 = 144元素，我们可以使用快速矩阵求幂模10^9 + 7计算适当的功率。记住潜伏的一个错误 - 这是你想要的F(n+1)。