蒙德里安的梦想

题目来源：AcWing

核心思想

参考实现

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 12, M = 1 << N;//每一列有2^n种状态
int n, m;
LL f[N][M];//n表示列数，m表示状态
//此题状态意为伸出去为1，不伸出去为0，所以这一列的“状态”表示为前一列的神不慎出去的情况
vector<int> state[M];
//二维数组，state[i]表示在i状态下，前一列列所有可行的状态
bool is_valid, st[M];
//存储每种状态是否有奇数个连续的0，如果奇数个0是无效状态，如果是偶数个零置为true。
int main()
{
    //总体思维：处理横着放的种数，剩下竖着放的只有一种，也就是n × 1 = n
    while (cin >> n >> m, n || m)//读入n和m，并且不是两个0即合法输入就继续读入
    {
        //注意：预处理是对广义上的单列处理
        //第一部分：预处理1
        //每一列一共2^n种状态，对于每种状态，先预处理每列不能有奇数个连续的0，否则竖着放不下
        for (int i = 0; i < 1 << n; i++)
        {
            int cnt = 0;//记录连续的0的个数
            is_valid = true;//初始化，某种状态没有奇数个连续的0则标记为true
            for(int j = 0; j < n; j++)//遍历这一列，从上到下
                if (i >> j & 1) 
                // i >> j位运算，表示i（i在此处是一种状态）的二进制数的第j位； 
                // &1为判断该位是否为1，如果为1进入if
                {
                    if (cnt & 1)
                    //这一位为1，看前面连续的0的个数，如果是奇数（cnt &1为真）则该状态不合法
                    {
                        is_valid = false;
                        break;
                    }
                    cnt = 0;
                    // 既然该位是1，并且前面不是奇数个0（经过上面的if判断），计数器清零。
                    // 其实清不清零没有影响
                }
                else 
                    cnt++;//否则的话该位还是0，则统计连续0的计数器++
            if (cnt & 1) 
                is_valid = false;//判断剩下的连续的0的个数
            st[i] = is_valid;//st数组储存状态i是否有奇数个连续的0的情况
        }
        //第二部分：预处理2
        //经过上面每种状态连续0的判断，已经筛掉一些状态
        //下面来看进一步的判断：看第i-2列伸出来的和第i-1列伸出去的是否冲突
        for (int i = 0; i < 1 << n; i++)//枚举一列的所有状态
        {
            state[i].clear();//清空上次操作（连续询问）遗留的状态，防止影响本次状态。
            for (int j = 0; j < 1 << n; j++)// 模拟上一列的所有状态
                if ((i & j) == 0 && st[i | j])
                // 第i-2列伸出来的 和第i-1列伸出来的不冲突(不在同一行) 
                // st[i | j]表示上一列的两个状态合并之后，必须还是没有奇数个0，才能进入if
                    state[i].push_back(j);
                    //j表示第i列“真正”可行的状态
                    //如果第i-1列的状态k和j不冲突则压入state数组中
                    //“真正”可行是指：既没有前后两列伸进伸出的冲突；又没有连续奇数个0
        }
        memset(f, 0, sizeof f);
        //全部初始化为0，因为是连续询问，这里是一个清空操作。
        //类似上面的state[i].clear()
        f[0][0] = 1;
        //首先注意本题解法是1 ~ m列映射到了0 ~ m-1列标上
        //按定义这里是：前第-1列都摆好，且从-1列到第0列伸出来的状态为0的方案数
        //这里没有-1列 = 没有伸出来 = 没有横着摆的 = 即这里第0列只有竖着摆这1种状态
        //且必须符合竖着也合法的状态才能被计入
        for (int i = 1; i <= m; i++)//遍历每一列：第m列合法范围是0 ~ m-1列
            for (int j = 0; j < 1 << n; j++)//遍历当前列（第i列）所有状态j
                for (auto k : state[j])// 遍历第i-1列的状态k，如果“真正”可行，就转移
                        f[i][j] += f[i - 1][k];
                        // 当前列的j方案数就等于之前的第i-1列所有能和j匹配的合法状态k的累加
        cout << f[m][0] << endl;
        //f[m][0]表示 前m-1列都处理完，并且第m-1列没有伸出来的所有方案数。
        //即整个棋盘处理完的方案数
    }
    return 0;
}