拼图 - 题目列表

形式化题目

给定 $n\times m$ 的方格图，用可以旋转的 L 型三格骨牌恰好铺满，求铺法数量对 $10^9+7$ 取模。这里 $m\leqslant 7$ ，但 $n$ 可能达到 $10^{15}$ 。

思路

先看小棋盘暴力：每次找第一个空格，枚举覆盖它的所有 L 型骨牌放法。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:56
 */
// brute.cpp：小数据暴力解，在小棋盘上递归枚举 L 型积木放置。
#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1000000007;
int n, m;
unordered_map<unsigned long long, long long> memo;

long long dfs(unsigned long long used) {
    unordered_map<unsigned long long, long long>::iterator it = memo.find(used);
    if (it != memo.end()) {
        return it->second;
    }

    int total = n * m;
    int first = -1;
    for (int i = 0; i < total; i++) {
        if ((used & (1ULL << i)) == 0) {
            first = i;
            break;
        }
    }
    if (first == -1) {
        return 1;
    }

    int row = first / m;
    int column = first % m;
    long long answer = 0;
    for (int top = row - 1; top <= row; top++) {
        for (int left = column - 1; left <= column; left++) {
            if (top < 0 || top + 1 >= n || left < 0 || left + 1 >= m) {
                continue;
            }
            for (int missing = 0; missing < 4; missing++) {
                unsigned long long placement = 0;
                bool contains_first = false;
                for (int dr = 0; dr < 2; dr++) {
                    for (int dc = 0; dc < 2; dc++) {
                        int index = dr * 2 + dc;
                        if (index == missing) {
                            continue;
                        }
                        int cell = (top + dr) * m + left + dc;
                        placement |= 1ULL << cell;
                        if (cell == first) {
                            contains_first = true;
                        }
                    }
                }
                if (!contains_first || (used & placement) != 0) {
                    continue;
                }
                answer += dfs(used | placement);
            }
        }
    }

    answer %= MOD;
    memo[used] = answer;
    return answer;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    if ((n * m) % 3 != 0) {
        cout << 0 << '\n';
        return 0;
    }
    cout << dfs(0) % MOD << '\n';
    return 0;
}

当行数较小时，可以用行轮廓 DP。处理到某一行时，用一个 m 位掩码表示这一行已经被上一行的骨牌占用的位置；填完这一行后，得到下一行将被占用的掩码。

行内转移

从当前行最左侧的空格开始，L 型骨牌只有三类相对放法：

当前行占连续两格，下一行占其中一格；
当前行占一格，下一行占右侧两格；
当前行占一格，下一行占左侧两格。

递归填满当前行，便得到状态转移 T[in][out]。

状态数最多为 $2^7=128$ 。一行一行转移需要 $O(n)$ ，无法处理 $n=10^{15}$ ，所以把转移计数看成矩阵 T，答案就是：

(T^n)_{0,0}

轮廓状态转移表

下面的表展示一次轮廓状态转移；1 表示对应列已经被占用。

当前行输入 `in`	本次放置	下一行输出 `out`	含义
`0000`	当前行占第 0、1 列，下一行占第 0 列	`0001`	L 块跨两行
`0000`	当前行占第 0 列，下一行占第 0、1 列	`0011`	L 块向下展开
`0100`	当前行占第 0 列，下一行占第 0、1 列	`0011`	第 1 列由上一行占用
`0010`	当前行占第 2 列，下一行占第 1、2 列	`0110`	下一行向左延伸

递归只从当前行最左空格继续，因此同一种铺法不会因放置顺序不同而重复计数；最终必须回到状态 0，表示最后一行没有骨牌伸出棋盘。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:56
 */
#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1000000007;
const int MAX_STATE = 1 << 7;

int width;
long long transition_count[MAX_STATE][MAX_STATE];

void fill_row(int start_mask, int current_mask, int next_mask, int column) {
    while (column < width && (current_mask & (1 << column)) != 0) {
        column++;
    }
    if (column == width) {
        transition_count[start_mask][next_mask]++;
        return;
    }

    // 当前行占连续两格，下一行占其中一格。
    if (column + 1 < width && (current_mask & (1 << (column + 1))) == 0) {
        int filled = current_mask | (1 << column) | (1 << (column + 1));
        if ((next_mask & (1 << column)) == 0) {
            fill_row(start_mask, filled, next_mask | (1 << column), column + 1);
        }
        if ((next_mask & (1 << (column + 1))) == 0) {
            fill_row(start_mask, filled, next_mask | (1 << (column + 1)), column + 1);
        }
    }

    // 当前行占一格，下一行占 column 和 column+1 两格。
    if (column + 1 < width
            && (next_mask & (1 << column)) == 0
            && (next_mask & (1 << (column + 1))) == 0) {
        fill_row(start_mask, current_mask | (1 << column),
                 next_mask | (1 << column) | (1 << (column + 1)), column + 1);
    }

    // 当前行占一格，下一行占 column-1 和 column 两格。
    if (column > 0
            && (next_mask & (1 << (column - 1))) == 0
            && (next_mask & (1 << column)) == 0) {
        fill_row(start_mask, current_mask | (1 << column),
                 next_mask | (1 << (column - 1)) | (1 << column), column + 1);
    }
}

typedef vector<vector<long long> > Matrix;

Matrix multiply(const Matrix &left, const Matrix &right) {
    int size = (int)left.size();
    Matrix result(size, vector<long long>(size, 0));
    for (int i = 0; i < size; i++) {
        for (int k = 0; k < size; k++) {
            if (left[i][k] == 0) {
                continue;
            }
            for (int j = 0; j < size; j++) {
                if (right[k][j] == 0) {
                    continue;
                }
                result[i][j] = (result[i][j] + left[i][k] * right[k][j]) % MOD;
            }
        }
    }
    return result;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long n;
    cin >> n >> width;

    if ((n % 3) * (width % 3) % 3 != 0) {
        cout << 0 << '\n';
        return 0;
    }

    int state_count = 1 << width;
    for (int mask = 0; mask < state_count; mask++) {
        fill_row(mask, mask, 0, 0);
    }

    Matrix result(state_count, vector<long long>(state_count, 0));
    Matrix base(state_count, vector<long long>(state_count, 0));
    for (int i = 0; i < state_count; i++) {
        result[i][i] = 1;
        for (int j = 0; j < state_count; j++) {
            base[i][j] = transition_count[i][j] % MOD;
        }
    }

    while (n > 0) {
        if (n & 1) {
            result = multiply(result, base);
        }
        base = multiply(base, base);
        n >>= 1;
    }

    cout << result[0][0] << '\n';
    return 0;
}

复杂度

设状态数为 $S=2^m$ 。预处理一行转移需要枚举所有状态及常数种放法，规模为 $O(Sm)$ ；矩阵快速幂需要 $O(S^3\log n)$ 时间，空间复杂度为 $O(S^2)$ 。

总结

当一维长度极大、另一维很小时，可以把小维度的边界占用情况作为状态，并把“一步推进一行”写成转移矩阵。快速幂将线性推进压缩到对数次矩阵乘法，最后从空状态回到空状态。

测试点编号	$n\le$	$m\le $
$1\sim 2$	$30$	$2$
$3\sim 4$	$6$	$6$
$5$	$100$	$6$
$6\sim 7$	$1000$	$6$
$8\sim 10$	$10^{15}$	$7$

拼图

目录

形式化题目

思路

行内转移

轮廓状态转移表

代码

复杂度

总结