Problem 1499 Gauss and Fibonacci一点小摘记

10175101159 edited 6 年，11 月前

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

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

3 0

Comments

服务

开源

关于我们