西電1232 求斐波拉契數列的後四位

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 好像     [cpp]   #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;   }