西電1232はフィボナッチの数列の後の四桁を求めます.

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
ベント
ソurce
LLL
mod=10000が見えます
100000個のデータがあれば、必ず重複があります.
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
", a[n]);
        else
            printf("%d
", a[n%30000]);
    }
    return 0;
}