铺瓷砖问题

• 链接：蒙德里安的梦想

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

• 例如当N=2，M=4时，共有5种方案。当N=2，M=3时，共有3种方案。

1.思路

• 填完所有横着摆放的小方块，竖着摆放的小方块也都确定了

• 先摆放横着的小方块，再摆放竖着的小方块

• $f[i][j]$表示：已经填完第i列，并且从i-1列伸出来的状态为j（二进制表示，1为横着摆放的小方块从i-1列伸到了第i列，而0表示没有伸出）的总方案数

• $f[i][j]$可以由$f[i-1][k]$转换而来，因为必须一列一列的摆放，且不能发生冲突，即j & k = 0（不能存在横着摆放的小方块既从i-2列伸出到i-1列，同时从i-1列伸出到第i列），且j | k中必须含有连续偶数个0（摆放第i-1列的时候，竖着的小方块必须能全部塞进去）

• 预处理st数组：求0到$1<<n$中的所有数中，是否有连续偶数个0

• 预处理state数组：求所有合法的二进制状态转换

• 代码附详细注释

2.Java代码

import java.util.*;

public class Main{

    static int N = 12, M = 1 << N;

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(true){
            int n = sc.nextInt(), m = sc.nextInt();
            if(n == 0 && m == 0) break;
            //存储所有合法状态
            List<Integer>[] state = new List[M];
            //存储一个二进制数是否存在连续偶数个0
            boolean[] st = new boolean[M];
            //dp数组
            long[][] f = new long[N][M];

            //预处理st数组：st[i]表示i的二进制表示是否有连续偶数个0，有为true
            for(int i = 0; i < 1 << n; i++){
                int cnt = 0;//连续偶数的个数
                st[i] = true;
                for(int j = 0; j < n; j++){
                    if((i >> j & 1) == 1){
                        //如果连续0为奇数个，无效状态
                        if((cnt & 1) == 1) st[i] = false;
                        //连续0位偶数个，置0判断后面是否还有连续偶数个0
                        else cnt = 0;
                    }else{
                        //累加0的个数
                        cnt++;
                    }
                }
                //扫描最后一段是否有连续偶数个0
                if((cnt & 1) == 1) st[i] = false;
            }

            //预处理合法状态，i和j之间的转换如果合法，则state[i].add(j)
            //判断f[k][i]是否可以由f[k-1][j]转换而来，也称为是否发生冲突
            for(int i = 0; i < 1 << n; i++){
                state[i] = new ArrayList<>();
                for(int j = 0; j < 1 << n; j++){
                    if((i & j) == 0 && st[i | j]){
                        state[i].add(j);
                    }
                }
            }

            //填完第0列，从第-1列伸过来的方块状态为0的方案数为1(空棋盘)
            f[0][0] = 1;

            //枚举每一列
            for(int i = 1; i <= m; i++){
                //枚举所有状态
                for(int j = 0; j < 1 << n; j++){
                    for(int k: state[j]){
                        //取出所有合法状态
                        f[i][j] += f[i-1][k];
                    }
                }
            }

            //答案就是填完第m列，且第m-1列伸过来的方块状态为0的方案数，从第0列开始算
            System.out.println(f[m][0]);

        }
    }
}