AcWing 291. 蒙德里安的梦想

◎

本节目标

预处理合法轮廓转移，按列推进统计矩形铺法。

题意与约束

用 1×2 多米诺骨牌铺满 n×m 棋盘，输入有多组，0 0 停止，输出每组铺法数。

第一反应与重复子问题

逐块选择会重复面对相同的列边界；只记录当前列哪些格子已被上一列横放骨牌占用即可。

状态定义与转移推导

mask 表示当前列已占用位，递归填充本列生成 nextMask。dp[mask] 向每个合法 nextMask 累加。

正确性依据

列内从上到下填第一个空格：要么横放并在下一列留下占用位，要么与下一行竖放，完整且不重不漏。

样例执行过程

2×3 的空轮廓经过三列后回到空轮廓，共有 3 种铺法；10×11 的结果需以 64 位保存。

代码实现

C++

C++17

#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
using namespace std;

long long countTilings(int n, int m) {
    if (n > m) {
        swap(n, m);
    }
    int states = 1 << n;
    vector<vector<int>> transitions(states);
    for (int mask = 0; mask < states; mask++) {
        function<void(int, int)> fill = [&](int row, int nextMask) {
            if (row == n) {
                transitions[mask].push_back(nextMask);
                return;
            }
            if (mask & (1 << row)) {
                fill(row + 1, nextMask);
            } else {
                fill(row + 1, nextMask | (1 << row));
                if (row + 1 < n && !(mask & (1 << (row + 1)))) {
                    fill(row + 2, nextMask);
                }
            }
        };
        fill(0, 0);
    }
    vector<long long> dp(states);
    vector<long long> next(states);
    dp[0] = 1;
    for (int column = 0; column < m; column++) {
        fill(next.begin(), next.end(), 0);
        for (int mask = 0; mask < states; mask++) {
            for (int nextMask : transitions[mask]) {
                next[nextMask] += dp[mask];
            }
        }
        dp.swap(next);
    }
    return dp[0];
}

#ifndef ALGORITHM_TUTORIAL_NO_MAIN
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    int m;
    while (cin >> n >> m && (n || m)) {
        cout << countTilings(n, m) << '\n';
    }
}
#endif

Python

Python 3

import sys


def count_tilings(n, m):
    n, m = min(n, m), max(n, m)
    transitions = [[] for _ in range(1 << n)]
    for mask in range(1 << n):
        def fill(row, next_mask):
            if row == n:
                transitions[mask].append(next_mask)
            elif mask >> row & 1:
                fill(row + 1, next_mask)
            else:
                fill(row + 1, next_mask | (1 << row))
                if row + 1 < n and not (mask >> (row + 1) & 1):
                    fill(row + 2, next_mask)
        fill(0, 0)
    dp = [0] * (1 << n)
    dp[0] = 1
    for _ in range(m):
        nxt = [0] * (1 << n)
        for mask, ways in enumerate(dp):
            for next_mask in transitions[mask]:
                nxt[next_mask] += ways
        dp = nxt
    return dp[0]


def main():
    output = []
    while True:
        line = sys.stdin.buffer.readline()
        if not line:
            break
        n, m = map(int, line.split())
        if n == 0 and m == 0:
            break
        output.append(str(count_tilings(n, m)))
    sys.stdout.write('\n'.join(output))


if __name__ == '__main__':
    main()

复杂度分析

令 w = min(n, m)、l = max(n, m)，并记所有合法轮廓转移的数量为 T。预处理合法状态与转移需要 O(2^w · w + T) 时间，随后逐列转移需要 O(T · l) 时间；滚动数组占用 O(2^w) 空间，转移表占用 O(T) 空间。

边界与易错点

1×1 无法铺满；必须处理终止标记前所有棋盘并在 0 0 后停止，不能把结果放进 32 位整数。

模式迁移

棋盘局部关系只跨相邻列时可用轮廓 DP；本章不进一步扩展到插头 DP。回到状态压缩动态规划。