uva 11310 - Delivery Debacle

題目出處：Uva

題目連結：11310 - Delivery Debacle

題目大意：link(luckycat)

解題方法：分析組合的情況。x代表空，o代表一單位的蛋糕，z代表為L形的蛋糕。

　　F[i]代表完整個寬度2長度i的組合數量，將他化簡成最左邊是填滿的情況。
　　F[i] = F[i-1] + 2*G[i-1] + 2*F[i-2]
　　x x x x　　　o x x x　　z z x x　　o z x x　
　　　　　　　 = 　　　　  + 　　　　　+
　　x x x x　　　o x x x　　z x x x　　z z x x
　　後兩個可以上下顛倒，因此要乘二。

　　G[i]代表缺一個，而總長度為i的組合數量。
　　G[i] = F[i-1] + F[i-2]
　　  x x　　　  x x　　  z x
　　　　　　=　　　　  +
　　x x x　　　o x x　　z z x

　　給定初始的F跟G即可解決此題。

注　　意：運算最大到10^18

代碼如下：