f738: 老鼠的數列
Tags : 優化 數列
Accepted rate : 13人/23人 ( 57% ) [非即時]
評分方式:
Tolerant

最近更新 : 2021-04-28 22:58

Content

老鼠喜歡研究數列

他最近再研究一個數列L,這個數列L的第i項是費氏數列的第i - 1項和第i + 1項的和

費氏數列f的索引從0開始:0, 1, 1, 2, 3, 5, 8, ...

L[1] = f[0] + f[2] = 0 + 1 = 1

L[5] = f[4] + f[6] = 3 + 8 = 11

他想請教你這個數列L第n項的值

由於數字很大,請你對答案取餘數

Input

多筆測資

每行一個n

1 <= n <= 106

Output

請你輸出L[n] mod 109+7

Sample Input #1
3
1
2
4
Sample Output #1
4
1
3
7
測資資訊:
記憶體限制: 30 MB
公開 測資點#0 (10%): 0.1s , <1K
公開 測資點#1 (10%): 0.1s , <1K
公開 測資點#2 (10%): 0.1s , <1M
公開 測資點#3 (10%): 0.1s , <1M
公開 測資點#4 (10%): 0.1s , <1M
公開 測資點#5 (50%): 1.5s , >50M
Hint :
Tags:
優化 數列
出處:
老鼠 [管理者:
fire5386 (皮卡丘)
]


ID User Problem Subject Hit Post Date
沒有發現任何「解題報告」