1184: 幫我求算一下斐波那契數吧

Time Limit:?1 Sec??Memory Limit:?128 MB
Submit:?221??Solved:?42
[Submit][Status][Web Board]

Description

AYY小朋友對斐波那契數非常感興趣，他知道f[1]=1,f[2]=1,并且從第三個斐波那契數開始f[n]=f[n-2]+f[n-1]（n>=3），可是AYY小朋友只會計算前十個斐波那契數，因此他向你請教，讓你幫忙計算第N個斐波那契數是多少，但是由于結果非常大，只需告訴他對1000000007取模的結果。

Input

多組測試數據每行一個n（1<=n<=2^32-1）

Output

輸出第n個斐波那契數的結果（對1000000007取模）

Sample Input

110100100010000

Sample Output

155687995182517691607271496360

HINT

Source

解析：n很大求斐波那契數，按照正常的思路不是超時就是爆內存。這時候就有一個的更好的求的方法：矩陣乘法。

矩陣乘法，通常可以縮減內存很省時，但是難理解。

矩陣快速冪：F(0) = 0F(1) = 1F(n) = F(n - 1) + F(n - 2) (n >= 2)
(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...)給出n，求F(n)，由于結果很大，輸出F(n) % 1000000007的結果即可。
引例?：求斐波那契數列的第?n?項?mod 1000000007?的值，?n <= 10?18?。

分析?：斐波那契數列的遞推式為?f(n) = f(n-1)+f(n-2)?，直接循環求出?f(n)?的時間復雜度是?O(n)?，對于題目中的數據范圍顯然無法承受。很明顯我們需要對數級別的算法。由于?f(n) = 1*f(n-1) + 1*f(n-2)?這樣的形式很類似于矩陣的乘法，所以我們可以先把這個問題復雜化一下，將遞推求解?f(n)?與?f(n-1)?的過程看作是某兩個矩陣相乘的結果，式子如下：

即：

所以我們只要不斷地乘以上面式子中的第二個矩陣（也就是第二個矩陣的冪）就能夠不斷遞推得到?f(n)?。但是這樣于解題沒有絲毫益處，反而使得常數變得更大（矩陣乘法的復雜度為立方級別）。所以我們就要利用矩陣乘法的一條重要性質：結合律。即矩陣?(A*B)*C = A*(B*C)?，證明過程可參見?2008?年國家集訓隊俞華程的論文。

有了結合律我們就可以用快速冪計算矩陣的冪，問題的復雜度順利降到了?O(logn)?。

#include<iostream> #include<memory.h> #include<cstdlib> #include<cstdio> #include<cmath> #include<cstring> #include<string> #include<cstdlib> #include<iomanip> #include<vector> #include<list> #include<map> #include<algorithm> typedef long long LL; const LL maxn=1000+10; const LL mod=1000000007; const int N=2; using namespace std; struct Matrix { LL m[N][N]; }; Matrix A= { 1,1, 1,0 }; Matrix I= { 1,0, 0,1 }; Matrix multi(Matrix a,Matrix b) { Matrix c; for(int i=0;i<N;i++) { for(int j=0;j<N;j++) { c.m[i][j]=0; for(int k=0;k<N;k++) c.m[i][j]+=a.m[i][k]*b.m[k][j]%mod; c.m[i][j]%=mod; } } return c; } Matrix power(Matrix A,int k) { Matrix ans=I,p=A; while(k) { if(k&1)ans=multi(ans,p);p=multi(p,p);k>>=1;} return ans; } int main() { int n; while(~scanf("%d",&n)) { Matrix ans =power(A,n-1); printf("%lld\n",ans.m[0][0]);//為什么是m[0][0]呢？這里花了 我幾個小時才搞明白。看下面的說明.......}return 0; }

說明：最后求出來的,假設它結果為然后還有乘與才等于右邊的? ?[f[n],f[n-1].

也就是發f【n】=m[0][0],矩陣的第0行第0列。

總結

以上是生活随笔為你收集整理的zcmu-1184（矩阵乘法）的全部內容，希望文章能夠幫你解決所遇到的問題。

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