题目分析

#include <iostream>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
int n, m;
long long f[12][1 << 11];
bool in_s[1 << 11];

int main()  {
   while (cin >> n >> m && n) {
       for (int i = 0 ; i < 1 << m ; i ++ ) {
           bool cnt = 0 , has_odd = 0; // has_odd初始化判断没有连续的状况，cnt 代表连续0的状态
           for (int j = 0 ; j < m ; j ++ ) 
                if (i >> j & 1) has_odd |= cnt , cnt = 0; // 如果上一个状态的cnt是第一次出现，
                那么表示不合法has_odd |= cnt = 1，连续0的数量清0
                else cnt ^= 1; // 如果为0，那么第一次cnt = 1 , 第二次cnt = 0 , 第三次cnt = 1 . . . 
            in_s[i] = cnt | has_odd ? 0 : 1;//如果cnt | has_odd = true ? 表示不合法 ， 为false表示合法
       }
       f[0][0] = 1;
       for (int i = 1 ; i <= n ; i ++ ) 
            for (int j = 0 ; j < 1 << m ; j ++ ) { // 第i行第j个状态
                f[i][j] = 0;
                for (int k = 0 ; k < 1 << m ; k ++ ) //第i - 1行的第K个状态
                    if ((j & k) == 0 && in_s[j | k]) // in_s表示预处理的所有合法的状态,  j & k == 0 ,合法情况没有两个并列的1
                        f[i][j] += f[i - 1][k];
            }
        cout << f[n][0] << endl;    
   }
}