主題

ZeroJudge - f996: N項的費氏數列 - Extreme 解題心得

Not In My Back Yard | 2022-04-17 00:00:01 | 巴幣 0 | 人氣 40

題目連結:


題目大意:
這題基本一樣,不過變數範圍有變。測試資料筆數 t 變為 1 ≦ t ≦ 10 ^ 5 、 n-Fibonacci 的 n 變為 2 ≦ n ≦ 15 且目標的第 k 項變為 1≦ k ≦ 2 ^ 60。



範例輸入:
5
2 5
3 2
10 12
12 1000
15 1125899906842624


範例輸出:
5
1
19
282446896
121395600


解題思維:
核心精神跟題目大意那題一致。不過本題不需要切換到暴力求解也可以過,但是由於原先(題目大意那題)的程式碼在利用矩陣快速冪求解時的計算量是
某某矩陣 × answer
其中 answer 是一個 n × n 的矩陣。

但是根據核心精神,實際上的 answer 可以縮減成一個 n × 1 (或 1 × n,端看實作方式)的矩陣,便可以大幅度減少原先不必要的計算量(因為原先這些多餘的計算量會在本題導致超時)。




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

創作回應

相關創作

更多創作