The Fourth Dimension Space

枯葉北風(fēng)寒，忽然年以殘，念往昔，語默心酸。二十光陰無一物，韶光賤，寐難安；不畏形影單，道途阻且慢，哪曲折，如渡飛湍。斬浪劈波酬壯志，同把酒，共言歡！ -如夢(mèng)令

導(dǎo)航

<

2009年3月

>

日

一

二

三

四

五

六

22

23

24

25

26

27

28

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

22

25

29

31

1

2

3

4

統(tǒng)計(jì)

隨筆 - 414
文章 - 13
評(píng)論 - 521
引用 - 0

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

CMU CV Group

搜索

閱讀排行榜

評(píng)論排行榜

ZOJ 2105 矩陣乘法(求線性常系數(shù)差分方程第N項(xiàng))

DIY群上說可以用暴力循環(huán)節(jié)的方法來做，的確也是不錯(cuò)的，不過練題的本質(zhì)在于學(xué)到新的東西，所以就用矩陣乘法敲了，恩感覺收獲還是蠻大的，掌握了和矩陣相關(guān)的很多運(yùn)算。

#include<iostream>

#include<algorithm>

using namespace std;

struct matrix

{

int n,m;

int a[2][2];

matrix operator *(matrix other)

{

int i,j;

matrix res;

res.n=n;

res.m=other.m;

for(i=0;i<n;i++)

for(j=0;j<m;j++)

{

res.a[i][j]=0;

for(int k=0;k<m;k++)

{

res.a[i][j]+=a[i][k]*other.a[k][j];

if(res.a[i][j]>=7)

res.a[i][j]%=7;

}

return res;

}

matrix operator +(matrix other)

{

matrix res;

for(int i=0;i<n;i++)

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

{

res.a[i][j]=a[i][j]+other.a[i][j];

if(res.a[i][j]>=7)

res.a[i][j]%=7;

}

return res;

}

};

matrix a;

matrix ans;

int A,B,n;

matrix g(int k)//算A^k

{

matrix t;

if(k==1)

return a;

if(k&1)

{

t=g(k>>1);

t=t*t;

t=t*a;

}

else

{

t=g(k>>1);

t=t*t;

}

return t;

}

void init()

{

a.n=2;a.m=2;

a.a[0][0]=0;

a.a[0][1]=1;

a.a[1][0]=B;

a.a[1][1]=A;

//////////////////////////////////////////////////////////////////////////

ans.n=2;

ans.m=1;

ans.a[0][0]=1;

ans.a[1][0]=1;

}

int main()

{

int i,j;

while(scanf("%d%d%d",&A,&B,&n)!=EOF)

{

if(A==0&&B==0&&n==0)

break;

if(n==1||n==2)

{

printf("1\n");

continue;

}

init();

a=g(n-2);

ans=a*ans;

printf("%d\n",ans.a[1][0]);

}

return 0;

}

posted on 2010-05-21 22:31 abilitytao 閱讀(1433) 評(píng)論(0) 編輯收藏引用

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。




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

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品