当前位置:首页 > 递推 > 正文
NOI2.3-1760菲波那契数列(2)
6098+

题目大意:有n次询问,每次询问一个数k,请回答第k个斐波那契数是多少?

题目描述

菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1,接下来每个数都等于前面2个数之和。
给出一个正整数a,要求菲波那契数列中第a个数对1000取模的结果是多少。

输入

第1行是测试数据的组数n,后面跟着n行输入。每组测试数据占1行,包括一个正整数a(1 <= a <= 1000000)。

输出

n行,每行输出对应一个输入。输出应是一个正整数,为菲波那契数列中第a个数对1000取模得到的结果。

样例输入

4
5
2
19
1

样例输出

5
1
181
1

解题思路

这是经典的地推题目,先赋初值,然后根据关系式递推求解。

询问次数没说,但如果问10000次而且每次都是第几十万个的时候,每次回答都重新算一遍会浪费时间,故可以先把斐波那契数列一次性先算出来,保存到数组中,对每次询问只需要O(1)的时间进行回答。

程序实现

About

坚决不Copy代码!

本文标签:,,

NOI2.3-1760菲波那契数列(2):等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!