題目連結：
題目大意：
而這次要問的是，有多少種正方形貨物（一樣，貨物大小可以是 1 ～ L 之間任意值）之放法使得從左到右看與從右到左看是一樣的（即迴文）？將方法數取除以 10007 的餘數後輸出。
範例輸入：
1
2
3
4
範例輸出：
1
2
2
4
解題思維：
當 L = n 時，我們可以看到其方法數為以下總和：
頭、尾各放一個邊長為 1 的正方形，中間的空缺即代表著長度為 n - 2 的通道。
頭、尾各放一個邊長為 2 的正方形，中間的空缺即代表著長度為 n - 4 的通道。
……
頭、尾各放一個邊長為 floor(n ÷ 2) 的正方形，中間的空缺即代表著長度為 n - 2 × floor(n ÷ 2) 的通道。
其中，floor() 代表向下取整，對於正數來說等同無條件捨去。
由上可知如果我們定 Di 為長度 i 時的方法數，則
Di ＝ Di-2 + Di-4 + …… + Di-2×floor(i ÷ 2)
而 D1 ＝ 1 、 D2 ＝ 2 。
不過當我們按照上述遞迴式，利用動態規劃（Dynamic Programming，DP）求出幾個項次之後，我們可以看到方法數形成的數列為以下：
1 、 2 、 2 、 4 、 4 、 8 、 8 、 16 、 16 、 32 、 32 、 64 、 64 、……
似乎隱含著 Di 之值為 2 ^ (floor(i ÷ 2))。
而這確實是如此，以下為證明（以下將 floor 運算省略為單一「÷」，即該除法代表整數除法）：
當 i ＝ 1 、 2 時，D1 ＝ 2 ^ (1 ÷ 2) ＝ 2 ^ 0 ＝ 1 、 D2 ＝ 2 ^ (2 ÷ 2) ＝ 2 ^ 1 ＝ 2。
假設 i ＝ k - 1 、 k 時命題成立，則
當 i ＝ k + 1 時， Dk+1 ＝ Dk-1 + (Dk-3 + Dk-5 + ……) ＝ 2Dk-1 ＝ 2 × 2 ^ ((k - 1) ÷ 2) ＝ 2 ^ ((k + 1) ÷ 2)，命題也成立。
當 i ＝ k + 2 時， Dk+2 ＝ Dk + (Dk-2 + Dk-4 + ……) ＝ 2Dk ＝ 2 × 2 ^ (k ÷ 2) ＝ 2 ^ ((k + 2) ÷ 2)，命題也成立。
因此根據數學歸納法，Di ＝ 2 ^ (i ÷ 2) 之命題成立。
所以所求之長度為 L 之方法數即為 2 ^ (floor(L ÷ 2)) 除以 10007 取餘數之值。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人
