poj3070 Fibonacci（矩阵快速幂模板）

#include<iostream>
using namespace std;
typedef long long LL;

struct mat{
	int m[2][2];
};

mat mul(mat a,mat b){
	mat ans;
	for(int i=0;i<2;i++){
		for(int j=0;j<2;j++){
			ans.m[i][j]=0;
			for(int k=0;k<2;k++){
				ans.m[i][j]+=a.m[i][k]*b.m[k][j];
			}
			ans.m[i][j]%=10000;
		}
	}
	return ans;
}

mat qp(mat a,LL b){
	mat ans={
	1,0,
	0,1
	};
	mat tem=a;
	while(b){
		if(b&1)
			ans=mul(ans,tem);
			tem=mul(tem,tem);
			b>>=1;
	}
	return ans;
}


int main(){
	LL n;
	mat a={
		1,1,
		1,0
	};
	while(cin>>n&&n!=-1){
		mat tem=qp(a,n);
		cout<<tem.m[0][1]<<endl;
	}
}