信息学奥赛一本通 1188：菲波那契数列(2)

【题目描述】

菲波那契数列是指这样的数列: 数列的第一个和第二个数都为<span id="MathJax-Span-2" class="mrow"><span id="MathJax-Span-3" class="mn">11，接下来每个数都等于前面<span id="MathJax-Span-5" class="mrow"><span id="MathJax-Span-6" class="mn">22个数之和。

给出一个正整数<span id="MathJax-Span-8" class="mrow"><span id="MathJax-Span-9" class="mi">aa，要求菲波那契数列中第<span id="MathJax-Span-11" class="mrow"><span id="MathJax-Span-12" class="mi">aa个数对<span id="MathJax-Span-14" class="mrow"><span id="MathJax-Span-15" class="mn">10001000取模的结果是多少。

【输入】

第<span id="MathJax-Span-17" class="mrow"><span id="MathJax-Span-18" class="mn">11行是测试数据的组数<span id="MathJax-Span-20" class="mrow"><span id="MathJax-Span-21" class="mi">nn，后面跟着<span id="MathJax-Span-23" class="mrow"><span id="MathJax-Span-24" class="mi">nn行输入。每组测试数据占1行，包括一个正整数<span id="MathJax-Span-26" class="mrow"><span id="MathJax-Span-27" class="mi">a<span id="MathJax-Span-28" class="mo">(<span id="MathJax-Span-29" class="mn">1<span id="MathJax-Span-30" class="mo">≤<span id="MathJax-Span-31" class="mi">a<span id="MathJax-Span-32" class="mo">≤<span id="MathJax-Span-33" class="mn">1000000<span id="MathJax-Span-34" class="mo">)a(1≤a≤1000000)。

【输出】

<span id="MathJax-Span-36" class="mrow"><span id="MathJax-Span-37" class="mi">nn行，每行输出对应一个输入。输出应是一个正整数，为菲波那契数列中第<span id="MathJax-Span-39" class="mrow"><span id="MathJax-Span-40" class="mi">aa个数对<span id="MathJax-Span-42" class="mrow"><span id="MathJax-Span-43" class="mn">10001000取模得到的结果。

【输入样例】

4
5
2
19
1

【输出样例】

5
1
181
1

 noip更多资料

链接：https://pan.baidu.com/s/1gOOOlCqxtPxgusGKya55Ag?pwd=05d3

#include <iostream>
 using namespace std;
 int main()
 {
     int n;
     int a[200];          //输入的第N个数字
     int f[1000001];    //将1000000个斐波那契数取1000的模都求出来
     f[1]=1;
     f[2]=1;
     cin>>n;
     for(int i=0;i<n;i++)
     {
         cin>>a[i];
     }
     for(int i=3;i<1000001;i++)
     {
         f[i]=(f[i-1]+f[i-2])%1000;           //高精度取模
     }
     for(int i=0;i<n;i++)
     {
         cout<<f[a[i]]<<endl;        //将输入的数字a[i]当成脚标用于f[]中，求出输入数字的斐波那契数取模的结果
     }
     return 0;
 }