91久久精一区二区三区大全,久久精品国产国产精品四凭,亚洲欧美国产精品专区久久

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

DIY群上說可以用暴力循環節的方法來做，的確也是不錯的，不過練題的本質在于學到新的東西，所以就用矩陣乘法敲了，恩感覺收獲還是蠻大的，掌握了和矩陣相關的很多運算。

#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 閱讀(1419) 評論(0) 編輯收藏引用

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



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

The Fourth Dimension Space

導航

統計

常用鏈接

留言簿(16)

隨筆檔案

文章檔案

Blogs in Computer Vision and Algorithm

友情鏈接

搜索

最新評論

閱讀排行榜

評論排行榜

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