PKU2411-Mondriaan's Dream

題目：http://poj.org/problem?id=2411

求寬度n、高度m的棋盤格上，塞滿2*1骨牌的方法數有多少種？(至多11*11)


程式碼：http://codepad.org/uJQlfsZ1
基本就是狀態壓縮
我們按一條條橫行來檢討
1是有填方塊的格子
0是「種子」，下一行相應點一定會長出1 (也就是直立)

首先先枚舉第一行的可能狀態，0可以任意擺放、1必須連著兩格放，是為legal函數
接下來的轉移由[i-1][j]->[i][k]，如何判定j是否可以轉移到k呢？
好比說j是111001把j反相得j2=000110
顯而易見，因為種子一定要在下一輪長大
所以k有1的部分至少得和j2一樣才行，j2有1、k也得有1 (是為picky)

根據j2，剩下是0的部分來講、k是自由的
只要把剩下部分套legal函數判斷是否有躺好就可以(是為blocky)

最後記得開Long long，經典狀態壓縮ACget！

(這題我從知道題目到現在AC就寫了兩年…)