题解 | #蒙德的梦#

题目链接

PEEK147 蒙德的梦

题目描述

荷兰画家皮特·蒙德里安（Piet Mondrian）对矩形填充情有独钟。在一场梦中，他想用若干块 $1 \times 2$ 的小矩形（可以水平或竖直摆放）完全覆盖一块 $M \times N$ 的大矩形。

请你帮助蒙德计算：给定 $M$ 和 $N$ ，不同填充方案的数量。若无法完全覆盖，则答案为 $0$ 。

需要注意的是，大矩形是定向的，即若两种方案通过翻转或旋转得到，但铺砌形状不同，也视为不同的方案。

解题思路

这是一个经典的棋盘覆盖计数问题，由于某一维的长度 $M$ 通常较小（例如 $M \le 11$ ），非常适合使用状态压缩动态规划（也常被称为轮廓线 DP）来解决。

核心思想

我们的核心思想是逐列填充这个 $M \times N$ 的矩形。当我们决定如何填充第 $i$ 列时，我们唯一需要关心的“历史信息”是第 $i-1$ 列的哪些格子有横向的 $1 \times 2$ 骨牌伸了过来，占用了第 $i$ 列的位置。这个“历史信息”就是所谓的轮廓线状态。

我们可以用一个 $M$ 位的二进制数来表示这个轮廓线状态，从而进行动态规划。

1. 初步判断与预处理

奇偶性判断: 一个 $1 \times 2$ 的骨牌覆盖两个格子。因此，要完全覆盖 $M \times N$ 的矩形，总面积 $M \cdot N$ 必须是偶数。如果 $M \cdot N$ 是奇数，则无法覆盖，方案数为 $0$ 。
维度统一: 为了方便处理，我们可以规定 $M$ 是较小的维度。由于 $M \times N$ 的矩形和 $N \times M$ 的矩形的填充方案数是一样的，若 $M > N$ ，我们可以交换它们。

2. 状态定义

我们定义 $dp[i][mask]$ 表示：已经成功铺满前 $i-1$ 列，且第 $i-1$ 列向第 $i$ 列伸出骨牌的状态为 $mask$ 时的方案数。

$i$ : 列的编号，从 $0$ 到 $N$ 。
$mask$ : 一个 $M$ 位的二进制整数。 $mask$ 的第 $j$ 位为 $1$ ，表示 $(j, i-1)$ 处的格子放了一个横向骨牌，该骨牌占据了 $(j, i)$ 的位置。 $mask$ 的第 $j$ 位为 $0$ ，表示 $(j, i)$ 位置没有被上一列伸过来的骨牌占据。

3. 状态转移

我们的目标是根据 $dp[i][\dots]$ 的所有值，计算出 $dp[i+1][\dots]$ 的所有值。

对于一个给定的 $dp[i][prev\_mask]$ ，它表示前 $i-1$ 列已铺好，且对第 $i$ 列的影响是 $prev\_mask$ 。现在我们需要铺第 $i$ 列。

第 $i$ 列的某些格子可能已经被 $prev\_mask$ 占了。我们需要用新的骨牌（横向或纵向）铺满第 $i$ 列所有剩下的空格。铺设的结果会对第 $i+1$ 列产生影响，这个影响就是 $next\_mask$ 。

我们可以通过一个深度优先搜索（DFS）函数来枚举在给定 $prev\_mask$ 的情况下，所有合法的铺设第 $i$ 列的方式，并计算出每种方式对应的 $next\_mask$ 。

$dfs(row, next\_mask)$ :

含义: 在处理第 $i$ 列时，当前考虑到第 $row$ 行，且已确定的对下一列的影响为 $next\_mask$ 。
基准情形: 当 $row = M$ 时，说明第 $i$ 列的所有格子都已成功处理。我们找到了一种从 $prev\_mask$ 到 $next\_mask$ 的有效过渡。于是，我们将方案数累加： $dp[i+1][next\_mask] += dp[i][prev\_mask]$
递归过程:
1. 如果 $(row, i)$ 已被 $prev\_mask$ 占据（即 $prev\_mask$ 的第 $row$ 位为 $1$ ），我们无法在此处放置新骨牌。直接进入下一行： $dfs(row + 1, next\_mask)$ 。
2. 如果 $(row, i)$ 未被占据：
  - 选择1：放一个横向骨牌。这个骨牌会占据 $(row, i)$ 和 $(row, i+1)$ 。这会影响下一列，所以我们将 $next\_mask$ 的第 $row$ 位置为 $1$ 。然后处理下一行： $dfs(row + 1, next\_mask \text{ | } (1 \ll row))$ 。
  - 选择2：放一个竖向骨牌。这个骨牌会占据 $(row, i)$ 和 $(row+1, i)$ 。这要求 $(row+1, i)$ 也必须是空闲的（即 $row+1 < M$ 且 $prev\_mask$ 的第 $row+1$ 位为 $0$ ）。这个骨牌不影响下一列，所以 $next\_mask$ 不变。由于一次性处理了两行，我们直接跳到第 $row+2$ 行： $dfs(row + 2, next\_mask)$ 。

4. 初始状态与最终答案

初始状态: $dp[0][0] = 1$ 。这表示在开始铺第 $0$ 列之前，我们已经“铺好”了前 $-1$ 列，对第 $0$ 列的影响为 $0$ （即没有任何骨牌伸过来），这种情况只有一种（什么都不做）。
最终答案: $dp[N][0]$ 。这表示铺满了全部 $N$ 列，并且没有骨牌伸出到不存在的第 $N+1$ 列。

代码

cpp
java
python

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

using namespace std;

int m, n;
long long dp[12][1 << 12];

void dfs(int col, int row, int prev_mask, int current_mask) {
    if (row == m) {
        dp[col + 1][current_mask] += dp[col][prev_mask];
        return;
    }

    // 如果当前单元格已被左侧的骨牌占据
    if ((prev_mask >> row) & 1) {
        dfs(col, row + 1, prev_mask, current_mask);
    } else {
        // 尝试放置一个 1x2 的横向骨牌
        dfs(col, row + 1, prev_mask, current_mask | (1 << row));

        // 尝试放置一个 2x1 的竖向骨牌
        if (row + 1 < m && !((prev_mask >> (row + 1)) & 1)) {
            dfs(col, row + 2, prev_mask, current_mask);
        }
    }
}

void solve() {
    cin >> m >> n;
    if (m > n) swap(m, n);

    if ((m * n) % 2 != 0) {
        cout << 0 << endl;
        return;
    }

    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;

    for (int i = 0; i < n; ++i) { // 遍历每一列
        for (int j = 0; j < (1 << m); ++j) { // 遍历所有可能的上一列状态
            if (dp[i][j] > 0) {
                dfs(i, 0, j, 0);
            }
        }
    }

    cout << dp[n][0] << endl;
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

import java.util.Scanner;
import java.util.Arrays;

public class Main {
    private static int m, n;
    private static long[][] dp;

    private static void dfs(int col, int row, int prevMask, int currentMask) {
        if (row == m) {
            dp[col + 1][currentMask] += dp[col][prevMask];
            return;
        }

        // 如果当前单元格已被左侧的骨牌占据
        if (((prevMask >> row) & 1) == 1) {
            dfs(col, row + 1, prevMask, currentMask);
        } else {
            // 尝试放置一个 1x2 的横向骨牌
            dfs(col, row + 1, prevMask, currentMask | (1 << row));

            // 尝试放置一个 2x1 的竖向骨牌
            if (row + 1 < m && ((prevMask >> (row + 1)) & 1) == 0) {
                dfs(col, row + 2, prevMask, currentMask);
            }
        }
    }

    public static void solve() {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            m = sc.nextInt();
            n = sc.nextInt();

            if (m > n) {
                int temp = m;
                m = n;
                n = temp;
            }

            if ((m * n) % 2 != 0) {
                System.out.println(0);
                continue;
            }

            dp = new long[n + 1][1 << m];
            for (long[] row : dp) {
                Arrays.fill(row, 0);
            }
            dp[0][0] = 1;

            for (int i = 0; i < n; i++) { // 遍历每一列
                for (int j = 0; j < (1 << m); j++) { // 遍历所有可能的上一列状态
                    if (dp[i][j] > 0) {
                        dfs(i, 0, j, 0);
                    }
                }
            }

            System.out.println(dp[n][0]);
        }
    }

    public static void main(String[] args) {
        solve();
    }
}

import sys

def solve():
    m, n = map(int, sys.stdin.readline().split())
    if m > n:
        m, n = n, m

    if (m * n) % 2 != 0:
        print(0)
        return

    dp = [[0] * (1 << m) for _ in range(n + 1)]
    dp[0][0] = 1

    memo = {}
    def get_transitions(prev_mask):
        if prev_mask in memo:
            return memo[prev_mask]

        transitions = []
        
        def dfs(row, current_mask):
            if row == m:
                transitions.append(current_mask)
                return

            if (prev_mask >> row) & 1:
                dfs(row + 1, current_mask)
            else:
                # 放置横向骨牌
                dfs(row + 1, current_mask | (1 << row))
                # 放置竖向骨牌
                if row + 1 < m and not ((prev_mask >> (row + 1)) & 1):
                    dfs(row + 2, current_mask)
        
        dfs(0, 0)
        memo[prev_mask] = transitions
        return transitions

    for i in range(n):
        memo.clear()
        for prev_mask in range(1 << m):
            if dp[i][prev_mask] == 0:
                continue
            
            transitions = get_transitions(prev_mask)
            for next_mask in transitions:
                dp[i + 1][next_mask] += dp[i][prev_mask]

    print(dp[n][0])


T = int(sys.stdin.readline())
for _ in range(T):
    solve()

算法及复杂度

算法: 状态压缩动态规划。
时间复杂度: $O(N \cdot 2^M \cdot C)$ , 其中 $C$ 是填充一列的平均计算时间。通过 DFS 枚举一列的填充方式，其可能的路径数与斐波那契数增长类似，大致为 $\phi^M$ （ $\phi$ 为黄金分割率）。因此，一个粗略的上限是 $O(N \cdot 2^M \cdot 2^M) = O(N \cdot 4^M)$ ，但由于状态转移的稀疏性，实际运行速度远快于此，更接近 $O(N \cdot 3^M)$ 。
空间复杂度: $O(N \cdot 2^M)$ ，用于存储 DP 状态表。可以通过滚动数组优化到 $O(2^M)$ 。