Problem 1499 Gauss and Fibonacci一点小摘记

10175101159 edited 6 年,8 月前

题意即求$Fibonacci$数列${f_{n}}$的前$n$项和$S_{n}$。
在网上看到了关于$Fibonacci$数列一个有趣的性质:$S_{n}=f_{n+2}-1$。
于是本题转化为求一个$Fibonacci$数,但项数很大可以考虑矩阵快速幂。

现对公式尝试证明如下:
注意到$1+S_{n}=f_{2}+f_{1}+f_{2}+f_{3}+\cdots+f_{n}=f_{3}+f_{2}+f_{3}+\cdots+f_{n}=f_{4}+f_{3}+\cdots+f_{n}=\cdots=f_{n+1}+f_{n}=f_{n+2}$
因而$S_{n}=f_{n+2}-1$

Comments