posts - 100,  comments - 15,  trackbacks - 0
/*
 * 3070.cpp
 *  
 *  Created on: 2010-10-2
 *      Author: wyiu
 
*/
#include 
<cstdio>
using namespace std;
struct Matrix
{
    
int a11, a12;
    
int a21, a22;
};

Matrix mutilMatrix(Matrix a, Matrix b)
{
    Matrix c;
    c.a11 
= (a.a11*b.a11+a.a12*b.a21 ) % 10000;
    c.a12 
= (a.a11*b.a12+a.a12*b.a22 ) % 10000;
    c.a21 
= (a.a21*b.a11+a.a22*b.a21 ) % 10000;
    c.a22 
= (a.a21*b.a12+a.a22*b.a22 ) % 10000;
    
return c;

}

Matrix powerMatrix(
int n)
{
    
if(n == 0)
    {
        Matrix m0 ;
        m0.a11
=1;
        m0.a12
=0;
        m0.a21
=0;
        m0.a22
=1;
        
return  m0;
    }
    
else
    {
        Matrix a, b;
        a 
= powerMatrix(n/2);
        b 
= mutilMatrix(a, a);
        
if(n%2 != 0)
        {
            Matrix m1 ;
            m1.a11
=1;
            m1.a12
=1;
            m1.a21
=1;
            m1.a22
=0;

            b 
= mutilMatrix(b, m1);
        }
        
return b;
    }

}

int main()
{
    
int n;
    
while(scanf("%d"&n) != EOF)
    {
        
if(n == -1)
            
break;

        Matrix r 
= powerMatrix(n);

        printf(
"%d\n", r.a12);
        fflush(stdout);
    }
    
return 0;
}
posted on 2010-10-03 16:41 wyiu 阅读(226) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理