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