斐波那契

[编程题]斐波那契

热度指数：4 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$Keven$ 特别喜欢斐波那契数列，已知 $fib_1=1$ ， $fib_2=1$ ，对于 $n>=3$ ， $fib_{n}=fib_{n-2}+fib_{n-1}$ ，并且他想知道斐波那契前 $n$ 项平方和是多少？

为了防止答案过大，请将最后的答案模 $1e9+7$

输入描述:

第一行一个整数 $n$ （ $1<=n<=1e18$ ）

输出描述:

在一行中输出斐波那契数列的前 $n$ 项平方和模 $1e9+7$

示例1

输入

输出

说明

算法知识视频讲解

wyzxlhx

发表于 2019-12-21 21:44:59

先来看看一张图：在图中，我们发现，最大矩形的面积即是我们要求的答案

Nikola_Tesla

发表于 2019-12-27 15:59:28

首先用数学归纳法证明斐波那契数列前n项平方和等于 f[n] * f[n+1];假设第 n 项时满足前n项平方和等于 f[n] * f[n+1];那么第 n+1 项时应该是 f[n] * f[n+1] + f[n+1] * f[n+1]= f[n+1] * (f[n] + f [n 展开全文

zbwang

发表于 2022-12-30 12:13:46

#include <iostream> #include <algorithm> #include <string> #include <cstring> #define LL long long const LL mod=1e9+7; using n 展开全文

想玩飞盘的伊登在debug

发表于 2020-08-14 15:23:55

1 * 1 + 2 * 2 + 3 * 3 + 5 * 5 + 8 * 8... n * n = n * (n+1)证明:

sunrise__sunrise

发表于 2020-07-17 23:48:46

matrixquickpow #include <iostream> #include <cstdio> #include <cstring> using namespace std; const int MOD = 1e9+7; typedef long lon 展开全文

Uncle_drew

发表于 2020-01-02 12:08:09

Link:斐波那契斐波那契 Description: Keven 特别喜欢斐波那契数列，已知,f[1]=f[2]=1,对于 n>=3f[n]=f[n-2]+fib[n-1] 并且他想知道斐波那契前n项平方和是多少？为了防止答案过大，请将最后的答案模1e9+7 输入描述: 第一行一个整数 n 展开全文