資源限制
時間限制：1.0s ? 內存限制：256.0MB
問題描述
Fibonacci數(shù)列的遞推公式為：Fn=Fn-1+Fn-2椭懊，其中F1=F2=1氧猬。
當n比較大時坏瘩，F(xiàn)n也非常大，現(xiàn)在我們想知道妄均，F(xiàn)n除以10007的余數(shù)是多少。
輸入格式
輸入包含一個整數(shù)n禁熏。
輸出格式
輸出一行邑彪，包含一個整數(shù)，表示Fn除以10007的余數(shù)宙彪。
樣例輸入
10
樣例輸出
55
說明：在本題中有巧，答案是要求Fn除以10007的余數(shù)，因此我們只要能算出這個余數(shù)即可灵汪，而不需要先計算出Fn的準確值柑潦，再將計算的結果除以10007取余數(shù)，直接計算余數(shù)往往比先算出原數(shù)再取余簡單览露。
樣例輸入
22
樣例輸出
7704
數(shù)據(jù)規(guī)模與約定
1 <= n <= 1,000,000譬胎。
斐波拉契數(shù)列是一個很經典的結構（0、1偏化、1镐侯、2苟翻、3、5沈条、8诅炉、13屋厘、21月而、34、……）仲翎，也引申出了很多問題铛漓，先以本道題為例浓恶。
（1）遞歸求解
構造遞歸函數(shù)，每次計算調用該函數(shù)湿镀，直到算出結果伐憾。
···
#include <iostream>
using namespace std;
int f(int n){
? ? ? ? return n<=2?1:(f(n-1)+f(n-2))%10007;
}
int main()
{
? ? int n,i;
? ? cin>>n;
? ? cout<<f(n);
? ? return 0;
}
···
但是這個做法運行超時，只得到了30分蒸矛，原因是遞歸存在大量的重復運算胸嘴。
f(5)=f(4)+f(3)=f(3)+f(2)+f(2)+f(1)=f(2)+f(1)+3=5
計算f(5)劣像，f(3)算了2次，f(2)算了3次耳奕，f(1)算了2次吮铭。
（2）遞推求解
用數(shù)組表示該數(shù)列，利用遞推式前項得到后項進行計算得出結果。
···
#include <iostream>
using namespace std;
int main()
{
? ? int n,i;
? ? cin>>n;
? ? int* a=new int [n];
? ? a[0]=1;
? ? a[1]=1;
? ? for(i=2;i<n;i++)
? ? {
? ? ? ? a[i]=(a[i-1]+a[i-2])%10007;
? ? }
? ? cout<<a[n-1];
? ? return 0;
}
···
這樣已經滿足要求了纸肉，當然還有更快的方法，參考鏈接：
https://www.zhihu.com/question/28062458/answer/39763094
另外柏肪，還有一些典型的斐波拉契數(shù)列問題
有n個臺階烦味，你每次只能跨一階或兩階，上樓有幾種方法柏靶？
第一個月初有一對剛誕生的兔子
第二個月之后（第三個月初）它們可以生育
每月每對可生育的兔子會誕生下一對新兔子
兔子永不死去
一年以后可以繁殖多少對兔子溃论？
參考網址：
https://baike.baidu.com/item/%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97/99145?fromtitle=%E6%96%90%E6%B3%A2%E6%8B%89%E5%A5%91%E6%95%B0%E5%88%97&fromid=10078434&fr=aladdin
