題意

　　用矩陣乘法求fibonacci數(shù)列的第n項。

Solution

　　矩乘入門題啊，題目把題解已經(jīng)說的很清楚里= =。

　　矩乘其實很簡單，通過自己YY或者是搜索對于一個遞推公式求出它所對應(yīng)的矩陣，然后套個快速冪就可以迅速求解第n項。

1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<queue> 6 #include<cstring> 7 #define mp make_pair 8 #define pb push_back 9 #define first fi 10 #define second se 11 #define pw(x) (1ll << (x)) 12 #define sz(x) ((int)(x).size()) 13 #define all(x) (x).begin(),(x).end() 14 #define rep(i,l,r) for(int i=(l);i<(r);i++) 15 #define per(i,r,l) for(int i=(r);i>=(l);i--) 16 #define FOR(i,l,r) for(int i=(l);i<=(r);i++) 17 #define eps 1e-9 18 #define PIE acos(-1) 19 #define cl(a,b) memset(a,b,sizeof(a)) 20 #define fastio ios::sync_with_stdio(false);cin.tie(0); 21 #define lson l , mid , ls 22 #define rson mid + 1 , r , rs 23 #define ls (rt<<1) 24 #define rs (ls|1) 25 #define INF 0x3f3f3f3f 26 #define LINF 0x3f3f3f3f3f3f3f3f 27 #define freopen freopen("in.txt","r",stdin); 28 #define cfin ifstream cin("in.txt"); 29 #define lowbit(x) (x&(-x)) 30 #define sqr(a) a*a 31 #define ll long long 32 #define ull unsigned long long 33 #define vi vector<int> 34 #define pii pair<int, int> 35 #define dd(x) cout << #x << " = " << (x) << ", " 36 #define de(x) cout << #x << " = " << (x) << "\n" 37 #define endl "\n" 38 using namespace std; 39 //********************************** 40 const int mod=1e4; 41 typedef vector<vi> mat; 42 //********************************** 43 mat mul(mat& a,mat& b) 44 { 45 mat c(2,vi(2)); 46 rep(i,0,2)rep(j,0,2)rep(k,0,2) 47 c[i][j]+=(a[i][k]*b[k][j]),c[i][j]%=mod; 48 return c; 49 } 50 mat qpow(mat a,int b) 51 { 52 mat c(2,vi(2)); 53 c[0][0]=c[1][1]=1;c[1][0]=c[0][1]=0; 54 while(b){ 55 if(b&1)c=mul(c,a); 56 a=mul(a,a); 57 b>>=1; 58 } 59 return c; 60 } 61 //********************************** 62 int main() 63 { 64 int n; 65 while(cin>>n,~n){ 66 mat v(2,vi(2));v[0][0]=1;v[0][1]=1;v[1][0]=1;v[1][1]=0; 67 v=qpow(v,n); 68 cout<<v[1][0]<<endl; 69 } 70 return 0; 71 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/klaycf/p/9682980.html

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。