題意:
(from luckycat)
解法:
直接講的話，他的遞迴式就是跟費波那契數列的關係類似：
f[ n ] =解釋一下的話，當 n > 2 時，可以把當前情況 f[ n ] 分成兩個部分，
{ 1, if n = 0
{ 2, if n = 1
{ f[ n-1 ] + f[ n-2 ], if n > 1
就是 由中間那條線反射回來的光線數 與 由另一邊的線反射回來的光線數，
而 前者 其實就是 f[ n-1 ] 的情況加上一次的反射，
而 後者 是 f[ n-2 ] 的情況加上兩次的反射且經由中間那條線。
TAG: BigNum, Math, DP
注意: 要用大數
程式碼:
沒有留言:
張貼留言
任何意見都樂意傾聽