為生存而奔跑

:: 首頁 :: 聯系 :: 聚合

:: 管理

271 Posts :: 0 Stories :: 58 Comments :: 0 Trackbacks

留言簿(5)

我參與的團隊

隨筆分類

隨筆檔案

相冊

Girl

搜索

積分與排名

積分 - 328415
排名 - 74

閱讀排行榜

評論排行榜

【矩陣問題】PKU 3070

pku 3070
題目要求計算Fibonacci數列的第n項最后4位。因為n可以很大(0 ≤ n ≤ 1,000,000,000)。因此直接計算在時限內是不可能的（有多個case）。題目還給出了計算的方法：表示成矩陣連乘的形式為

求第n項的后4位，相當于求第n項模10000的余數。而矩陣的乘法滿足邊乘邊模。矩陣乘法還滿足結合律，所以可以先計算出上面的一個矩陣的2的冪次方的值，記錄下來。然后對于每一個n，將它表示成2進制。如當n=5時，只需計算一次矩陣乘法：1次方乘以4次方。當n=1000000000時最多只需計算29次矩陣乘法2^29 = 536870912）

#include<iostream>

#include<algorithm>

#include<string>

#include<vector>

#include<cmath>

#include<map>

using namespace std;

int m[31][4],fact[31];

int n;

void init()

{

fact[1]=1;

m[1][0]=1; m[1][1]=1; m[1][2]=1; m[1][3]=0;

for(int i=2;i<=30;i++)

{

m[i][0]=(m[i-1][0]*m[i-1][0]+m[i-1][1]*m[i-1][2])%10000;

m[i][1]=(m[i-1][0]*m[i-1][1]+m[i-1][1]*m[i-1][3])%10000;

m[i][2]=(m[i-1][2]*m[i-1][0]+m[i-1][3]*m[i-1][2])%10000;

m[i][3]=(m[i-1][2]*m[i-1][1]+m[i-1][3]*m[i-1][3])%10000;

fact[i]=fact[i-1]*2;

}

void solve()

{

bool vis[31]={0}; // 對n表示成2進制

for(int i=30;i>0;i--)

if(n>=fact[i])

{

n-=fact[i];

vis[i]=1;

}

int res[4]={1,0,0,1}; //單位矩陣

int tmp[4];

for(int i=1;i<=30;i++)

{

if(vis[i])

{

tmp[0]=(res[0]*m[i][0]+res[1]*m[i][2])%10000;

tmp[1]=(res[0]*m[i][1]+res[1]*m[i][3])%10000;

tmp[2]=(res[2]*m[i][0]+res[3]*m[i][2])%10000;

tmp[3]=(res[2]*m[i][1]+res[3]*m[i][3])%10000;

for(int j=0;j<4;j++)

res[j]=tmp[j];

}

printf("%d\n",res[1]);

}

int main()

{

init();

while(scanf("%d",&n)!=EOF&&n!=-1)

{

solve();

}

posted on 2009-08-17 10:57 baby-fly 閱讀(259) 評論(0) 編輯收藏引用所屬分類: Algorithm

只有注冊用戶登錄后才能發表評論。
【推薦】100%開源！大型工業跨平臺軟件C++源碼提供，建模，組態！

相關文章: 二分搜索找上下界算法導論上的歸并排序 PKU 2184 dp PKU 2392 多重背包 PKU 2823 Sliding Window 單調隊列 HDU 3415 單調隊列 t CRecordSet KMP字符串模式匹配詳解 HDU 3450 樹狀數組離散化

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理