状态压缩动态规划

蒙德里安的梦想

求把 $N\times M$ 的棋盘分割成若干个 $1\times 2$ 的长方形，有多少种方案。

注意到：

• 当我们放完所有的横向小方格后（图中红色摆放好之后），竖向小方格的放置方案唯一确定
• 也就是如何求所有的横向小方格摆放方式