难度简单223
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
示例 1：
输入：n = 2 输出：1
示例 2：
输入：n = 5 输出：5
提示：
0 <= n <= 100
思路:斐波那契数列，一个老生常谈的问题。
1.直接根据公式线性递推:f[i]=f[i-1]+f[i-2]，可以使用滚动数组或双元素优化空间占用。
class Solution {
public:
int fib(int n) {
if(!n) return 0;
const int mod = 1e9 + 7;
int preF = 0, F = 1, temp;
for(int i = 2; i <= n; ++ i) {
temp = F;
F = (F + preF) % mod;
preF = temp;
}
return F;
}
};2.矩阵快速幂。我们可以用矩阵的乘法来表示斐波那契的运算，则有：
如果我们从F[0]、F[1]递推到第n项，那么公式如下：
此时我们对矩阵乘法用快速幂去加快前一项的运算即可。
class Solution {
public:
static const int mod = 1e9 + 7;
struct martix {
long long mat[2][2];
martix operator * (const martix m) {
martix temp;
temp.mat[0][0] = (mat[0][0] * m.mat[0][0] % mod + mat[0][1] * m.mat[1][0] % mod) % mod;
temp.mat[0][1] = (mat[0][0] * m.mat[0][1] % mod + mat[0][1] * m.mat[1][1] % mod) % mod;
temp.mat[1][0] = (mat[1][0] * m.mat[0][0] % mod + mat[1][1] * m.mat[1][0] % mod) % mod;
temp.mat[1][1] = (mat[1][0] * m.mat[0][1] % mod + mat[1][1] * m.mat[1][1] % mod) % mod;
return temp;
}
};
int fib(int n) {
martix base, m;
base.mat[0][0] = 1; base.mat[0][1] = 0; base.mat[1][0] = 0; base.mat[1][1] = 1;
m.mat[0][0] = 1; m.mat[0][1] = 1; m.mat[1][0] = 1; m.mat[1][1] = 0;
while(n) {
if(n & 1) {
base = base * m;
}
n >>= 1;
m = m * m;
}
return base.mat[0][1];
}
};