LOJ6291 小 L 进阶的斐波那契数列游戏

题目链接:小 L 进阶的斐波那契数列游戏

(刷新以获取数学公式)

题意

求\(\sum_{i=1}^{n} F_i^2\)

\(F_i\)是斐波那契数,\(n≤1e15\)

题解

方法一

原式=\(F_n * F_{n+1}\)

数学归纳易证.

方法二

让我感兴趣的是这种做法.

构造矩阵快速幂.记\(S_i = \sum_{i=1}^{n} F_i^2\)

那么 \(S_i = S_{i-1} + F_i^2\)

而\(F_i^2 = F_{i-1}^2 + 2*F_{i-1}*F_{i-2} + F_{i-2}^2\), \(F_{i-1}*F_{i-2}=F_{i-2}^2+F_{i-2}*F_{i-3}\)

所以我们维护一个记录 \(S_n\), \(F_{n+1}^2\), \(F_{n}^2\), \(F_{n+1}*F_n\)的矩阵即可.