轮廓线 DP：网格图上的状态压缩艺术

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

// 求解用 1x2 骨牌铺满 N x M 棋盘的方案数
long long dominoTiling(int N, int M) {
    if ((N * M) % 2 != 0) return 0; // 奇数个格子绝对铺不满
    
    // 如果 M 比较大，可以交换 N 和 M，保证状压的位数最小
    if (N < M) swap(N, M);

    int max_S = 1 << M;
    // 使用滚动数组，只有当前格和上一格的状态
    long long dp[2][1 << 20]; 
    memset(dp, 0, sizeof(dp));

    int old = 0, now = 1;
    dp[old][0] = 1; // 初始状态：空棋盘，轮廓线没有任何凸出，方案数为 1

    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < M; ++j) {
            swap(now, old); // 滚动
            memset(dp[now], 0, sizeof(long long) * max_S); // 清空当前状态

            for (int S = 0; S < max_S; ++S) {
                if (!dp[old][S]) continue;

                if (S & (1 << j)) {
                    // 情况 1：当前格已被占用，直接跳过，将该位清零
                    dp[now][S ^ (1 << j)] += dp[old][S];
                } else {
                    // 情况 2：当前格为空，必须放置骨牌
                    
                    // 选项 A：竖放 (向下一行凸出，当前位变 1)
                    dp[now][S | (1 << j)] += dp[old][S];
                    
                    // 选项 B：横放 (占用右边一格，右边一位变 1，当前位保持 0)
                    if (j + 1 < M && !(S & (1 << (j + 1)))) {
                        dp[now][S | (1 << (j + 1))] += dp[old][S];
                    }
                }
            }
        }
    }

    // 最终状态：铺满且最后一行没有任何向下的凸出，即 S = 0
    return dp[now][0];
}

int main() {
    int N, M;
    while (cin >> N >> M && (N || M)) {
        cout << dominoTiling(N, M) << "\n";
    }
    return 0;
}