我們知道如果用記憶化搜索逐項遞推可以將復雜度降低到O（n）,但是對于更大規模的輸入，這個算法效率還是不夠高，那么我們考慮更高效的算法：

二階遞推：f(n+2)=(1 1) f(n+1)

? ? ? ? ? ? ? ? ?f(n+1) ?(1 0) ? f(n)

上面等式兩邊分別是矩陣，那么矩陣A就是等式右邊第一個式子。

只要求出A的n次，就可以求出f(n)。我們使用快速冪來求，這個算法的復雜度為O（logn）

?

#include <iostream> #include <cstddef> #include <cstring> #include <vector> using namespace std; typedef long long ll; const int mod=10000; typedef vector<ll> vec; typedef vector<vec> mat; mat mul(mat &a,mat &b){mat c(a.size(),vec(b[0].size()));for(int i=0;i<2;i++){for(int j=0;j<2;j++){for(int k=0;k<2;k++){c[i][j]+=a[i][k]*b[k][j];//c[i][j]%=mod;}}}return c; } mat pow(mat a,ll n){mat res(a.size(),vec(a.size()));for(int i=0;i<a.size();i++)res[i][i]=1;while(n>0){if(n&1){res=mul(res,a);n-=1;}else{a=mul(a,a);n/=2;}}return res; } ll solve(ll n){mat a(2,vec(2));a[0][0]=1;a[0][1]=1;a[1][0]=1;a[1][1]=0;a=pow(a,n);return a[1][0]; }int main(){ll n;while(cin>>n){cout<<solve(n)<<endl;}return 0; }

?

?

總結

以上是生活随笔為你收集整理的利用矩阵快速幂求斐波那契数列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。