斐波拉切数列（3种代码）

数列（3种代码）"/>

斐波拉切数列（3种代码）

大家都知道，斐波那契数列是满足如下性质的一个数列：

F_n = \left\{\begin{aligned} 1 \space (n \le 2) \\ F_{n-1}+F_{n-2} \space (n\ge 3) \end{aligned}\right.Fn​={1 (n≤2)Fn−1​+Fn−2​ (n≥3)​

请你求出 F_n \bmod 10^9 + 7Fn​mod109+7 的值。

输入格式(

一行一个正整数 nn

输出格式

输出一行一个整数表示答案。

输入输出样例

输入 #1复制

5

输出 #1复制

5

输入 #2复制

10

输出 #2复制

55

(以上来自洛谷)

1.

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e9 + 7;
int a[10010];
void fbnc(int n){if(n==1||n==2)a[n]=1;if(n==1)return;fbnc(n-1);a[n]=a[n-1]+a[n-2];a[n]%=maxn;
}
int main(){int n;scanf("%d",&n);fbnc(n);cout<<a[n];return 0;
}

2.

#include<bits/stdc++.h>
using namespace std;
const int m=1e9+7;
long long n;
struct jz{int a[110][110];jz operator *(jz b){jz tmp;for(int i=0;i<2;i++){for(int j=0;j<2;j++){tmp.a[i][j]=1ll*a[i][0]*b.a[0][j]%m;for(int k=1;