The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

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 阅读(1328) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理