求出 Σ(k=1~n) (fib[k])。

由於 n<41,其實可以直接模擬。

如果仔細算一下可以發現,Σ(k=1~n) (fib[k]) = fib[k+2]-1。

這樣搭配 矩陣冪次 最快可以在 lgn 求出,不過我還是只寫 O(n) 構造法而已。

我的code

http://snipt.org/zfim1

 

文章標籤
創作者介紹
創作者 jghs1328 的頭像
jghs1328

jghs1328

jghs1328 發表在 痞客邦 留言(0) 人氣()