2491.cpp

这是哈尔滨工业大学acmOJ的源代码

/* This Code is Submitted by wywcgs for Problem 2491 on 2007-06-01 at 12:42:56 */
#include <cstdio>
#include <cmath>

const int P = 10000;
 
void com(int);
void mul(int[][2], int[][2]);
 
int main()
{
	int n;

	while(scanf("%d", &n) != EOF && n >= 0)
		if(n < 2) printf("%d\n", n);
		else com(n-1);
	
	return 0;
}
 
void com(int n)
{
	int i, b, m[2][2] = { { 0, 1 }, { 1, 1 } }, unit[2][2] = { { 0, 1 }, { 1, 1 } };
	for(b = 31; (n&(1<<b)) == 0; b--);
	for(i = b-1; i >= 0; i--) {
		mul(m, m);
		if(n & (1<<i)) mul(m, unit);
	}
	printf("%d\n", m[1][1]);
}
void mul(int a[][2], int b[][2])
{
	int a1 = a[0][0]*b[0][0]+a[0][1]*b[1][0], a2 = a[0][0]*b[0][1]+a[0][1]*b[1][1];
	int b1 = a[1][0]*b[0][0]+a[1][1]*b[1][0], b2 = a[1][0]*b[0][1]+a[1][1]*b[1][1];
	a[0][0] = a1%P; a[0][1] = a2%P; a[1][0] = b1%P; a[1][1] = b2%P;
}