SPOJ CAKE3. Delicious Cake

Vjudge | SPOJ | TG

先複習一下 插頭 dp 大字典。本題顯然使用染色模型。輪廓線上只有 m 個位置,而且不需要 roll() 操作(不過生成的新插頭,要求前面的區分開來,所以我們還是用 m+1 來標記)。這樣搞得話,2×2 我們會算出答案等於 14,仔細觀察,是因為我們多算了下面兩種不合法的情況。

我們發現這類情況都是因為在前面的轉移中產生了刻痕,而使得後續的插頭合併不合法,需要進一步編碼。
我們可以給每個連通塊強行上一個顏色,不相同的顏色不可合併。但是因為原問題沒有顏色,這樣計數起來會比較麻煩(需要最小染色,並且必須保證相同顏色的連通塊必被合併)。
我們也可以暴力記錄 C(5,2) 個連通塊之間是否產生過刻痕,這樣合併的時候直接判斷即可。

刻痕的維護,首先每次狀態轉移,當前插頭都需要和相鄰兩個插頭(左插頭和上插頭)都標記刻痕。
其次,因為我們使用了最小表示,連通塊的記號會被 relable,因而編碼的時候也需要重新映射。
最後插頭合併的時候,刻痕信息也需要合併。

最後上一下高精度模板就好了。留個 OEIS 地址方便大家 debug。