盛日辉的博客
0%

EOJ 5201. Kaleidoscope（铺砖问题状压DP）

发表于 更新于 分类于

EOJ 5201. Kaleidoscope

读完题，心想这不就是个动态规划么，定义 $dp[i]$ 表示铺满 $i$ 行的方案数，然后从 $i-1$ 和 $i-2$ 行转移过来，特殊算一下两行的情况用来转移，这不就好了么。

但是写了八百遍调试了九千遍之后仍然不对。

后来意识到（当然也是问了 Gemini 得到了正确思路后），最后铺满，并不是只能从之前的铺满的状态转移过来，它完全可以从第 $i-1$ 行伸出一些到第 $i$ 行然后仍然可以铺满的。

所以这道题的正确思路是状压DP。

定义每一列的格子的占有情况为二进制数 $s$，其中 $1$ 表示有棋子 $0$ 表示没有棋子。用递归的方式分别计算所有状态对应的“下一个”状态是什么及其数量。

具体的看代码吧，这里想再说一下动态规划的初始值和最后的返回值为什么都是 $dp[0]$。因为 $dp[s]$ 可以理解成是第 $i - 1$ 行留给第 $i$ 行的状态是 $s$，一开始棋盘的空的，可以认为是第 $0$ 列（棋盘的列从 $1$ 开始）留给第 $1$ 列的是 $0$ 。同样的，当所有格子都铺满了，可以认为最后留给第 $m+1$ 列的状态是 $0$。用 Gemini 的话来说，$0$ 状态相当于「收口」。

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

# 状态压缩 DP
# 用二进制来表示每一列的棋子占有情况
# 预处理所有状态对应有哪些下一步的变化
# adj = [[(status, cnt), ...], ...] 
#   adj[s][i] = (ns, c) 从 s 到 ns 有 c 种情况
# 递归的对每一个 s 讨论
# 
# 动态规划（见下）


from collections import defaultdict


def dfs(cur: int, i: int, nxt: int) -> None:
    global memo
    if i > m:
        return
    if i == m:
        # 找到一个从 cur 到 nxt
        memo[nxt] += 1
        return
    if cur >> i & 1 == 0:  # 第 i 位为 0
        if i < m - 1 and cur >> (i + 1) & 1 == 0:  # 连着 2 位都是 0，有两种方案
            dfs(cur, i + 2, nxt)  # 用 2x1，nxt 不变
            dfs(cur, i + 2, nxt | (3 << i))  # 用 2x2，nxt 对应位填上
        dfs(cur, i + 1, nxt | (1 << i))  # 用 1x2
    else:  # 第 i 位为 1，nxt 不变
        dfs(cur, i + 1, nxt)


MOD = 998244353
n, m = list(map(int, input().split()))
total_status = 1 << m

# adj[s] = [(ns, cnt),...] 从 s 到 ns 有多少种
adj = []
memo = defaultdict(int)
for s in range(total_status):
    dfs(s, 0, 0)
    adj.append(list(memo.items()))
    memo.clear()

"""
# dp[i][s]：填完第 i 行后留给第 i+1 行的状态（前面假装补充一行一共 n+1 行）
# 初始：dp[0][0] = 1
# 最后答案是 dp[-1][0]（没有什么砖块留给后面了）
dp = [[0] * total_status for _ in range(n + 1)]
dp[0][0] = 1
for i in range(n):
    for s in range(total_status):
        if dp[i][s] == 0: continue
        for ns, cnt in adj[s]:
            dp[i + 1][ns] += dp[i][s] * cnt
            dp[i + 1][ns] %= MOD
print(dp[-1][0])
"""

# 空间优化
dp = [0] * total_status
dp[0] = 1
for i in range(n):
    ndp = [0] * total_status
    for s in range(total_status):
        if dp[s] == 0: continue
        for ns, cnt in adj[s]:
            ndp[ns] += cnt * dp[s]
            ndp[ns] %= MOD
    dp = ndp
print(dp[0])
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
// 注释见 Python 代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll MOD = 998244353;
int n, m;
int total_status;

struct Edge {
    int ns;
    ll cnt;
};

int main() {
    cin >> n >> m;

    total_status = 1 << m;
    vector<vector<Edge>> adj(total_status);

    vector<int> memo(1024);
    for (int cur = 0; cur < total_status; cur++) {
        auto dfs = [&](auto self, int i, int nxt) -> void {
            if (i == m) {
                memo[nxt]++;
                return;
            }
            if ((cur >> i) & 1) {
                self(self, i + 1, nxt);
            } else {
                if (i < m - 1 && (cur >> (i + 1) & 1) == 0) {
                    self(self, i + 2, nxt);
                    self(self, i + 2, nxt | (3 << i));
                }
                self(self, i + 1, nxt | (1 << i));
            }
        };

        dfs(dfs, 0, 0);

        for (int ns = 0; ns < total_status; ns++) {
            if (memo[ns] > 0) {
                adj[cur].push_back({ns, memo[ns]});
                memo[ns] = 0;
            }
        }
    }

    vector<ll> dp(total_status, 0);
    dp[0] = 1;
    for (int i = 0; i < n; i++) {
        vector<ll> ndp(total_status);
        for (int s = 0; s < total_status; s++) {
            if (dp[s] == 0) continue;
            for (auto &edge : adj[s]) {
                ndp[edge.ns] = (ndp[edge.ns] + (edge.cnt * dp[s]) % MOD) % MOD;
            }
        }
        dp = move(ndp);
    }

    cout << dp[0];
    return 0;
}