方法一:用公式时间O(1)
#include <bits/stdc++.h>
using namespace std;
int main()
{
double t=sqrt(5);
int n;cin>>n;
double fib_n=1.0/t*((pow((1+t)/2.0,n)-pow((1-t)/2.0,n)));
cout<<(long long)fib_n<<'\n';
return 0;
}
方法二:滚动+递推,时间O(n),空间O(1)
#include <bits/stdc++.h>
using namespace std;
const int mod=1e9+7;
int fib(int n)
{
if (n<=1) return 1;
int x,y,z;
x=y=1;
for (int i=2;i<=n;i++)
{
z=(x+y)%mod;
x=y;
y=z;
}
return z;
}
int main()
{
int n;cin>>n;
cout<<fib(n)<<'\n';
return 0;
}
方法三:矩阵运算(常规+矩阵快速幂)
常规矩阵运算
矩阵快速幂运算