主題

ZeroJudge - g556: 白色世界(困難版) 解題心得

Not In My Back Yard | 2021-12-19 00:00:05 | 巴幣 0 | 人氣 142

題目連結:


題目大意:
這題的加強版。其中 t 的範圍變為 1 ≦ t ≦ 300000,而 n 的範圍變為 1 ≦ n ≦ 10 ^ 18。



範例輸入:
範例輸入 #1
1
2

範例輸入 #2
2
3
10


範例輸出:
範例輸出 #1
2

範例輸出 #2
4
143


解題思維:
參見題目大意中給定的鏈結裡下方的心得,而因為 n 的範圍變得相當地大。因此我們需要使用類似計算費氏數列時的矩陣快速冪(如這題)。




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

創作回應

相關創作

更多創作