主題

ZeroJudge - f738: 老鼠的數列 解題心得

Not In My Back Yard | 2021-05-01 00:00:06 | 巴幣 0 | 人氣 67

題目連結:


題目大意:
已知費氏數列 F 為
F[0] = 0
F[1] = 1
F[n] = F[n - 1] + F[n - 2](對於 n > 1)

而現在我們定義另一數列 L,其值為
L[n] = F[n - 1] + F[n + 1](對於 n > 0)

輸入有多列,每列給定一正整數 n (1 ≦ n ≦ 10 ^ 6),試問 L[n] 之值為多少?將答案取除以 10 ^ 9 + 7 之餘數後輸出。



範例輸入:
3
1
2
4


範例輸出:
4
1
3
7


解題思維:
可以看到:
L[n - 2] = F[n - 3] + F[n - 1]
L[n - 1] = F[n - 2] + F[n]
而 L[n - 2] + L[n - 1] =
F[n - 3] + F[n - 2] + F[n - 1] + F[n]
而根據費氏數列的定義,我們可以得到
F[n - 1] + F[n + 1]
而此即為 L[n] 之值。

事實上,數列 L 即是盧卡斯數(Lucas Numbers。雖然其實 Lucas 的 s 在法文(這位數學家是法國人)中並不發音,所以應譯為「盧卡」,但是「盧卡斯」已成習慣)。不過原始數列的開頭為 2 和 1 ,而本題為 1 和 3 開頭。

因此我們可以參照費氏數列的建表方式(如這題),將 L[1] ~ L[1000000] 都先行求出來並存著。然後對於輸入什麼 n 值,就輸出對應的 L[n] 之值。

但是因為輸入資料量非常、異常地龐大,所以需要最佳化輸出入(如這題)。如果嫌這樣子的最佳化還不太夠,可以嘗試編譯器方面的最佳化選項(如這題)。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作