状态压缩dp
如果是1*3的话就改成(i & j & k)这样子
我没有能力用文字表述清楚这题的思想
建议搜视频来看

# include <bits/stdc++.h>

using namespace std;

long long n, m, f[20][1 << 11];

bool st[1 << 11];

int main()
{
    while(cin >> n >> m && n)
    {
        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 && cnt & 1) st[i] = false;
                else if(!(i >> j & 1)) cnt ++;
            if(cnt & 1) st[i] = false;
        }

        f[1][0] = 1;
        for(int i = 2; i <= m + 1; i ++)
        {
            for(int j = 0; j < 1 << n; j ++) f[i][j] = 0;
            for(int j = 0; j < 1 << n; j ++)
                for(int k = 0; k < 1 << n; k ++)
                    if(!(j & k) && st[j | k]) f[i][j] += f[i-1][k];
        }
        cout << f[m+1][0] << endl;
    }
}