#include using namespace std; typedef long long LL; const int N = 12; const int M = 1 << N; int n, m; LL f[N][M]; // 已经摆完前i列并且第i列的状态为j的所有方案 vector v[M]; // 对于每个状态而言,能转转移到它的状态有哪些,预处理一下(二维数组) int ok[M]; // 某种状态是否合法,就是是不是存在奇数个连续0 int main() { while (cin >> n >> m, n + m) { // ① 预处理:枚举行数n的每个二进制位,可以枚举出每种可能出现的状态对应的二进制表示,这些状态有些是不合法的 // 只有不存在连续奇数个数字0的状态才是合法的,一旦n确定了,这个有效状态是可以预处理出来的 for (int i = 0; i < 1 << n; i++) { int cnt = 0; // 连续0的个数 ok[i] = 1; // 初始设置此状态是合法的 for (int j = 0; j < n; j++) // 遍历此状态的每一个二进制位,开始检查 if (i >> j & 1) { // 如果本位是1,表示连续0发生中断,需要统计连续0的个数,并且记得清空cnt if (cnt & 1) { // 奇数个连续0, (cnt & 1) = (cnt % 2 >0) ok[i] = 0; // 连续0发生中断,此状态为不合法状态 break; // 不用再往后看了,一次失足就不挽救 } cnt = 0; // 连续个零计数重新开始 } else cnt++; // 连续0的计数器++ // 最后一个cnt++后,依然可能有连续奇数个,举个栗子:n=4=(0100)_2,完成数位枚举后,cnt=1,也就是高位存在奇数个0 if (cnt & 1) ok[i] = 0; } // ② 预处理:枚举每个状态,获取可能是从哪些有效状态转移过来 for (int i = 0; i < 1 << n; i++) { // 多组数据,每次预处理时清空一下 // vector v[M] 是一个二维数组,初始化比较麻烦,需要用循环遍历第一维,然后再v[i].clear()进行清空 v[i].clear(); // 状态i,从哪些状态转化而来? for (int j = 0; j < 1 << n; j++) // j为前序状态 // (1) i & j==0 同一行不能同时探出小方格,那样会有重叠 // (2) 解释一下ok[i | j] // 比如: 01000 | 10101 = 11101,描述当前完成状态叠加后的最终状态,在预处理的数组中找一下,是不是合法状态 if ((i & j) == 0 && ok[i | j]) v[i].push_back(j); } // 多组数据,每次清零 memset(f, 0, sizeof f); // 初始方案数 f[0][0] = 1; // 可以理解为 从虚拟的第0开始(第一个0),还没有向右探出小方格(第二个0),此时的方案数只有1种。 // 如果你想为什么不是0种,下面的递推关系就会让你明白,0做为基底,就啥也递推不出来了。 // DP正式开始 for (int i = 1; i <= m; i++) for (int j = 0; j < 1 << n; j++) // 遍历第i列的所有状态j for (auto k : v[j]) // 遍历第i-1列的所有状态k f[i][j] += f[i - 1][k]; // 每个合法状态,均需从它的前序有效状态转移而来 // 输出答案 cout << f[m][0] << endl; } return 0; }