2262.cpp

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

/*  This Code is Submitted by wywcgs for Problem 2262 on 2006-06-03 at 17:18:05 */ 
#include <cstdio>

const int N = 10000;

int main()
{
	int sn[10240], i, sum = 0;
	
	sn[0] = 1; sn[1] = 1; sum = 2;
	for(i = 2; i <= N; i++) {
		sn[i] = (sn[i-1]*2+sum-sn[i-1]) % N;
		sum = (sum+sn[i]) % N;
	}
	int n;
	while(scanf("%d", &n) != EOF && n != 0) {
		printf("%d\n", sn[n]);
	}
	
	return 0;
}