传送门

矩阵快速幂板题，写一道来练练手。

这一次在poj做题总算没忘了改万能库。

代码：

#include<iostream>
#include<cstdio>
#define mod 10000
#define A a[0][0]
#define B a[0][1]
#define C a[1][0]
#define D a[1][1]
using namespace std;
int n;
struct Matrix{int a[2][2];Matrix(){A=0,B=C=D=1;}};
inline Matrix operator*(Matrix a,Matrix b){
	Matrix ret;
	ret.A=(a.A*b.A+a.B*b.C)%mod;
	ret.B=(a.A*b.B+a.B*b.D)%mod;
	ret.C=(a.C*b.A+a.D*b.C)%mod;
	ret.D=(a.C*b.B+a.D*b.D)%mod;
	return ret;
}
inline int ksm(){
	if(n==0)return 0;
	if(n==1)return 1;
	n-=2;
	Matrix x,ret;
	while(n){
		if(n&1)ret=ret*x;
		x=x*x,n>>=1;
	}
	return ret.D;
}
int main(){
	while(scanf("%d",&n)&&~n)printf("%d\n",ksm());
	return 0;
}