http://poj.org/problem?id=3070

按已构造好的矩阵，那么该矩阵的n次方的右上角的数便是f[n]。

#include <stdio.h>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <stack>
#include <vector>
#include <math.h>
#include <string.h>
#include <queue>
#include <string>
#include <stdlib.h>
#include <algorithm>
#define LL long long
#define _LL __int64
#define eps 1e-12
#define PI acos(-1.0)
#define C 240
#define S 20
using namespace std;

const int maxn = 110;

struct matrix
{
	int mat[3][3];
	void init()
	{
		memset(mat,0,sizeof(mat));
		mat[1][1] = mat[2][2] = 1;
	}
}a;

matrix mul(matrix a, matrix b)
{
	matrix res;
	memset(res.mat,0,sizeof(res.mat));
	for(int i = 1; i <= 2; i++)
	{
		for(int k = 1; k <= 2; k++)
		{
			if(a.mat[i][k] == 0) continue;
			for(int j = 1; j <= 2; j++)
			{
				int t = a.mat[i][k]*b.mat[k][j];
				res.mat[i][j] = (res.mat[i][j] + t)%10000;
			}
		}
	}
	return res;
}

matrix pow(matrix a, int n)
{
	matrix res;
	res.init();

	while(n)
	{
		if(n&1)
			res = mul(res,a);
		a = mul(a,a);
		n >>= 1;
	}
	return res;
}

int main()
{
	int n;
	while(~scanf("%d",&n))
	{
		if(n == -1) break;
		a.mat[1][1] = a.mat[1][2] = a.mat[2][1] = 1;
		a.mat[2][2] = 0;

		matrix ans = pow(a,n);

		printf("%d\n",ans.mat[1][2]);
	}
	return 0;
}