斐波那契数列
描述
众所周知,斐波那契数列就是满足以下规则的数列
\(a_1=1,a_2=1,a_{n+2}=a_{n+1}+a_n\)
所以,我们现在要求该数列的第n项
输入
第一行一个整数T,表示数据组数
接下来的T行,每行一个整数n
输出
T行,每行一个整数,表示\(a_n\)
由于答案可能很大,结果对\(10^9+7\)取模
输入样例
3
5
9
100000
输出样例
5
34
911435502
数据范围与限制
对于30%的数据,\(T\leq100,n\leq200000\)
对于60%的数据,\(T\leq100,n\leq10^8\)
对于100%的数据,\(1\leq T\leq10^5,1\leq n\leq10^{18}\)
时间限制2秒,空间限制256M
信息
- ID
- 1009
- 难度
- 7
- 分类
- Fibonacci数列 、 矩阵乘法 、 数学 点击显示
- 标签
- (无)
- 递交数
- 43
- 已通过
- 2
- 通过率
- 5%
- 上传者