fibonacci - 找到斐波那契数的总和

Question

从 F(n) 计算斐波那契数之和的最有效方法是什么？至 F(m)哪里F(n)和 F(m)分别是第 n 个和第 m 个斐波那契数，0 =< n <= m <109(其中 F(0)=0，F(1)=1)。

例如，如果 n=0 , m=3 ，我们需要找到 F(0)+F(1)+F(2)+F(3) .

仅靠蛮力，n 的范围需要很长时间。和 m提及。如果可以通过矩阵求幂来完成，那么如何？

Answer 1

F(m+2) - F(n+2) - 2 ( discussion )

从字面上看，您的上限 m 的总和减去您的下限 n 的总和。