#include<iostream>
using namespace std;

int n;
void xiangcheng_fib(unsigned long a, unsigned long b, unsigned long c, unsigned long d)
{
	int fib(int n, unsigned long a, unsigned long b, unsigned long c, unsigned long d);
	fib(n / 2, (a * a + b * c) % 10000, (a * b + b * d) % 10000, (a * c + c * d) % 10000, (c * b + d * d) % 10000);
}

void jianyi_fib(unsigned long a, unsigned long b, unsigned long c, unsigned long d)
{
	int fib(int n, unsigned long a, unsigned long b, unsigned long c, unsigned long d);
	fib(n - 1, (a + b) % 10000, a, (c + d) % 10000, c);
}

int fib(int n, unsigned long a, unsigned long b, unsigned long c, unsigned long d)
{
	if(n == 0) return 0;
	else if(n == 1) return b;
	else if(n % 2 == 0) 
		xiangcheng_fib(a, b, c, d);
	else  //n % 2 != 0
		jianyi_fib(a, b, c, d);
}


int main()
{
	while(cin >> n) {
		if(n == -1) break;
		cout << fib(n, 1, 1, 1, 0) % 10000 << endl;
	}
	return 0;
}

• 绝对失误 写反了。。。而且也RT 贴出改正代码 (989) vince4053040 2010-02-04 16:33:58