主題

ZeroJudge - f354: 好多好多 ~ 好多正方形 解題心得

Not In My Back Yard | 2020-11-16 00:00:01

題目連結:


題目大意:
這題還有這題的輸入類似。有若干列輸入(約 10000 列),每列給定一正整數 L (L ≦ 1000000),代表通道的長度。

而這次要問的是,有多少種正方形貨物(一樣,貨物大小可以是 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 取餘數之值。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
57 巴幣: 0

相關創作

更多創作