http://acm.xidian.edu.cn/land/problem/detail?problem_id=1232&contest_id=22
Description
定义一个序列：f[0]=0,f[1]=1,f[n]=f[n-1]+f[n-2]。那么，f[10]是多少，f[100]是多少，f[1000]呢...
模拟的话显然最后结果非常大，现在只要你输出f[n]的最后四位，前面的0不输出，若答案为10000，输出0，若答案为10001，输出1.
0 ≤ n ≤ 1,000,000,000
Input
多组数据，每组一个n
Output
f[n]的最后四位
Sample Input
4
Sample Output
3
Hint
Source
LLL
看到mod=10000
而有1000000000个数据 那么一定有重复的
如果f（n）==f(1)&&f(n-1)==f(0) 那么这时候循环节就找到了 结果为15000 好像
#include<iostream>
#include<cstdio>
using namespace std;
int a[30001];
int main()
{
int n;
a[0] = 0;
a[1] = 1;
for(int i=2; i<=30000; i++)
a[i] = (a[i-1]%10000+a[i-2]%10000)%10000;
while(scanf("%d", &n)!=EOF)
{
if(n <= 30000)
printf("%d\n", a[n]);
else
printf("%d\n", a[n%30000]);
}
return 0;
}