吶...
TOJ還是不給submit，
不過我感覺是沒問題了，就先放上來吧
這題主要算是math題吧
我到現在還是搞不太懂就是
這題基本上最直觀的解法就是直接加上去
結果還是TLE...
仔細看數字有到百億...
我看學長AC的時間是零
又想到費氏數列其實是有公式的
就開始往「是否能直接帶入公式」的方向思考
讓時間從O(n)變成O(1)
結果一直爬文阿
已知費氏數列的公式了，費氏數列合的公式怎麼求也不知道
浪費了兩三張計算紙感覺都在耍白癡，像是寫了好幾行得出了s(n-1)+f(n)=s(n)之類的廢話
後來觀察了一下，突然發現s(i)=f(i+2)-1，就莫名其妙發現的規律
用程式跑幾個大數字也正確就是了
像前5項的和(1+1+2+3+5)=第7項(13)-1=12
然後就想說很高興的帶公式直接O(1)得解
結果發現一個致命問題...
不知道怎麼取mod...
又試了一段時間，結果還是放棄了阿...公式解>口<
不知不覺打了一堆幹話:3
總之後來發現了，原來費氏數列還有一種求法是O(logn)
來源網站
參考了一下，就實作看看，原理甚麼的不懂
畢竟我根本沒學過矩陣
然後就做出來了...
時間的話跟直接加比起來,當n=100000000(億)，
相加耗費2秒多，矩陣只要不到0.001秒
看來是沒問題了...
搞了一個晚上終於解決，只是原理不知道心就是有點癢癢的
比較一下費氏數列我已知的三個解法
1.加法 : O(n) ,易實作,足以應付大部分狀況
2.公式解 O(1) ,應該不會用到,而且不夠彈性,像這題就想不到方法取mod(可能是我太笨QQ)
3.矩陣 O(logn) ,數字特別大會TLE才需要用到(約超過10^8)
376.cpp(不能完全AC，但可以參考
更新(7/4
TOJ修好後發現一堆問題
可惡...果然沒那麼順利...
結果又爬了一堆文
硬生生地把矩陣的算法之類的搞懂
...
真的有夠麻煩...
反正...終於AC了...
376-2.cpp(AC正解版