题解 | #斐波那契数列#

对于，我们用递归完全可行，时间复杂度为，代码：

#include <iostream>
using namespace std;
const int N=1e6+9,mod=1e9+7;
int memo[N];
int f(int n){
    if(n<=2) return 1;
    if(memo[n]) return memo[n];
    return memo[n]=(f(n-1)+f(n-2))%mod;
}
int main() {
    int k;
    cin >> k;
    cout << f(k) << endl;
}
// 64 位输出请用 printf("%lld")

但是当级别时，我们要求，这时候就需要用到矩阵快速幂了，根据斐波拉契数列的递推式，斐波那契数列的矩阵递推式为：

其中初始条件为 ，转移矩阵记为 。

这样我们只需要计算，就可得到了，而这个通过矩阵快速幂，时间优化成。

#include<bits/stdc++.h>
#include <cstring>
using namespace std;
using ll=long long;
const int mod=1e9+7;
struct matrix{
    ll m[3][3];
    matrix(){
        memset(m, 0,sizeof(m));
    }
    matrix operator*(matrix& t) const{
        matrix res;
        for(int i=1;i<=2;i++){
            for(int j=1;j<=2;j++){
                for(int k=1;k<=2;k++){
                    res.m[i][j]=(res.m[i][j]+m[i][k]*t.m[k][j]%mod)%mod;
                }
            }
        }
        return res;
    }
};
int main() {
    int k;
    cin >> k;
    matrix b,M;
    b.m[1][1]=b.m[1][2]=b.m[2][1]=1;
    b.m[2][2]=0;
    M.m[1][1]=M.m[2][2]=1;
    k--;
    while(k){
        if(k&1) M=M*b;
        b=b*b;
        k>>=1; 
    }
    cout << M.m[1][1] << endl;
}
// 64 位输出请用 printf("%lld")

此外还有一个结论，斐波拉契数列的前项和。