求斐波那契数之和

本文介绍了求斐波那契数之和的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

计算从F(n)到F(m)的斐波那契数之和的最有效方法是什么，其中F(n)和F(m)分别是第n个和第m个斐波那契数，且0 =

What would be the most efficient way to calculate the sum of Fibonacci numbers from F(n) to F(m) where F(n) and F(m) are nth and mth Fibonacci numbers respectively and 0 =< n <= m <109 (with F(0)=0, F(1)=1).

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

For example, if n=0, m=3, we need to find F(0)+F(1)+F(2)+F(3).

仅通过蛮力，提到的n和m范围将花费很长时间.如果可以通过矩阵求幂来完成，那怎么办?

Just by brute force it will take long time for the range of n and m mentioned. If it can be done via matrix exponentiation then how?

推荐答案

F(m+2) - F(n+2) - 2(讨论)

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

Literally, the sum of your upper bound m, minus the sum of your lower bound n.