为什么结果不是f[m+1][0]

对啊，i从1开始的，不应该是m+1嘛
为什么循环不直接从i=0开始

后面还有个i-1呢，你从0开始不就直接越界了

真正的列是从0～m-1，m是不存在的，但第m列可以保证前m-1都计算好了

// st[j | k] == 1 表示 在 i 列状态 j， i - 1 列状态 k 的情况下是合法的.
那我为什么改成st[j]&&st[k]是错的啊

为什么f[0][0] = 1

捅出来！

感觉说法好奇怪哈哈哈

自己的一些理解:
https://www.acwing.com/solution/content/239291/

Orz

这里的预处理的循环条件为什么是i<1<<n 而不是i<1<<m 啊
有没有大佬解答一下

n行m列,预处理那边是对所有的状态进行处理，所以只管n就好了，应该是这样？

状态是竖着的，所以肯定是1<<n啊

朴素写法就是这里没搞懂

// 扫完后要判断一下最后一段有多少个连续的0 最后一段是什么意思？

比方一种状态的二进制是100100111000，最后这三个0就是最后一段

感谢，我在别的帖子问有人回答过我了，这里发下我的理解，请指正：

   //加上的话会对于形如 0001 ，000111，前面有奇数个0的进行判断(虽然是前导0，但因为有n的限制一定会遍历这么多位)，不加的话虽然j位为1，但cnt初始值为0，没有机会判断st，等出现0了，cnt才会++，但也要再出现1才会判断st,但正如000111他可能不会再出现1，却有奇数个0（不合法）所以我们需要再补充这句来判断下cnt

思路听懂了，但是第一步预处理搞不懂

就是对状态j进行枚举, 当出现连续的段有奇数个0时就置为false

非常清晰

楼主写的太好了！！我也研究了一下，写了更详细的代码解释：
https://www.acwing.com/solution/content/28088/
大佬们有需要可以看一哈。

tql

i >> j & 1 是什么意思?

奥 是取每一位的状态, 状压 二进制

这个运算顺序是先算 j & 1吗？

你好，运算顺序是先算i>>j 这句话是求i的二进制表示法中的第j位，然后这一位再和 1相与，看这一位是不是1，如果是1，就返回true

为什么f[1][1] = 1，第0列可以放置横这的小方块，桶到第一列吗？

可以的

另外f[1][1]不一定等于1，要看你n和m的值

好的，谢谢大佬！

st[j |k]这里有一列中的连续的0为偶数个，就可以吗？

是的，j|k ==i, i-1列的k状态和i列的j状态进行或运算， 将可以得到i列空格状态。

我写了详细的题解，你可以看看

你自己题解里写的对的，但是你这句话评论错了，“将可以得到i-1列空格状态”

嗯嗯，谢谢大佬指正

秒哇，老哥。但是我还是不太理解预处理过程是怎样的，为什么要枚举 1 << M

应该是枚举 1<<n, 是状态压缩dp的套路，每一列一共有2^n个状态

可以

谢谢大佬，这个题解写的特别详细

同样的思路用python写的，提示超时，哪位大佬可以优化一下？？？

# 输入示例
while True:
    n, m = map(int, input().split())    # n行m列
    st = [True for i in range(1<<n)]
    if  n|m:  # n||m    
        for i in range(1<<n):
            cnt = 0
            for j in range(n):
                if (i>>j) & 1:
                    if cnt & 1: st[i] = False
                    cnt = 0
                else: cnt += 1
            if cnt & 1: st[i] = False

        # 初始化dp数组
        dp = [[0 for i in range(1<<n)] for j in range(m+1)]
        dp[0][0] = 1

        # 状态计算
        for i in range(1, m+1):
            for j in range(0, 1<<n):
                for k in range(0, 1<<n):
                    if ((j & k) ==0) and st[j|k]:
                        dp[i][j] += dp[i-1][k]
        print(dp[m][0])
    else:
        break

• 当格子总数为奇数(nm)%2 ==1时，答案一定为0，因为12的长方格子填，一定是填上了偶数个格子。
• 下面是代码【我太懒了，直接看的你的代码，非常感谢，下面的代码也是在你的基础上加的注释和特判输出0】

while True:
    # n行m列
    n, m = map(int, input().split())    
    # 储存有效状态
    st = [True for i in range(1<<n)]
    # n/m中有一个为0则退出
    if n|m:
        if not n*m % 2 == 0:
            print(0)
            continue
        # i = 0 ~ 2^n-1
        for i in range(1<<n):
            cnt = 0
            # j = 0 ~ n-1【遍历这个状态的每一行，即从i-1列是否有东西伸到第i列】
            for j in range(n):
                # 如果状态i的第j位为1，那么当前这个状态下第j行不可能放置方块【即有方块伸到第i列，那么第i列的j行不可能放置方块】
                if (i>>j) & 1:
                    # 如果cnt为奇数，那么该状态不行【任意一个位置进来，那么cnt一定都要为偶数】
                    # 对状态i置false
                    if cnt & 1: st[i] = False
                    cnt = 0
                # 否则的话，才可以放置方块
                else: cnt += 1
            # 如果cnt为奇数
            if cnt & 1: st[i] = False

        # 初始化dp数组，一共m+1列，每一列2^n-1个状态
        dp = [[0 for i in range(1<<n)] for j in range(m+1)]
        # 第0列有且只能是伸出0个为一种状态【第0列不可能从-1列伸出任何一个方块】
        dp[0][0] = 1

        # 状态计算，遍历每一列
        for i in range(1, m+1):
            # 每一个状态
            for j in range(0, 1<<n):
                # 遍历上一列的状态
                for k in range(0, 1<<n):
                    # 上一列的状态j能否转移到当前状态k，并且st是合法的状态
                    if ((j & k) ==0) and st[j|k]:
                        # 如果能转移且合法，则方法数加上所有可以转移过来的方法
                        dp[i][j] += dp[i-1][k]
        # 最终的答案为最后一列，且伸出0个方块出来【刚好填完最后一列，且不伸出最后一列】
        print(dp[m][0])
    else:
        break

为什么第一列不需要特判答案还是正确的？？

这里要从f[i][j]的集合表示讲起， 状态表示 f[i][j]: 前i-1列已经确定，且从第i-1列伸出的小方格在第i列的状态为j 的方案数。
棋盘是从第0列开始，没有-1列，所以第0列状态为0。棋盘为空，这种状态记录为一种方案。f[0][0] = 1;