為生存而奔跑

:: 首頁(yè) :: 聯(lián)系 :: 聚合

:: 管理

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

留言簿(5)

我參與的團(tuán)隊(duì)

隨筆分類

隨筆檔案

相冊(cè)

Girl

搜索

積分與排名

積分 - 330206
排名 - 74

閱讀排行榜

評(píng)論排行榜

【矩陣問(wèn)題】PKU 3070

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

求第n項(xiàng)的后4位，相當(dāng)于求第n項(xiàng)模10000的余數(shù)。而矩陣的乘法滿足邊乘邊模。矩陣乘法還滿足結(jié)合律，所以可以先計(jì)算出上面的一個(gè)矩陣的2的冪次方的值，記錄下來(lái)。然后對(duì)于每一個(gè)n，將它表示成2進(jìn)制。如當(dāng)n=5時(shí)，只需計(jì)算一次矩陣乘法：1次方乘以4次方。當(dāng)n=1000000000時(shí)最多只需計(jì)算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}; // 對(duì)n表示成2進(jìn)制

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 閱讀(264) 評(píng)論(0) 編輯收藏引用所屬分類: Algorithm

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。
【推薦】100%開(kāi)源！大型工業(yè)跨平臺(tái)軟件C++源碼提供，建模，組態(tài)！

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

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問(wèn) Chat2DB 管理