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;

}