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$的矩阵即可.