狀態壓縮 DP 入門：N×M 地板鋪 1×2/2×1 磚塊方案數

在 N×M 格子中用 1×2（橫放）與 2×1（豎放）磚塊完全覆蓋，求方案數模 1e9+7。M ≤ 10，適合狀態壓縮 DP。

狀態定義：逐行逐格遞推

掃描順序：第 0 行第 0 格 → 第 0 行第 1 格 → ... → 第 N-1 行第 M-1 格。
狀態用 M 位二進制數表示下一行各格是否被上一行豎放磚塊佔用：

• 第 j 位 = 1：該格已被上方豎磚佔用（本行無需放磚，直接跳過）
• 第 j 位 = 0：該格空閒，需在本行放磚

單格決策（位置 (i,j)，狀態 mask）

1. mask 第 j 位 = 1：被佔用，跳過 → 處理 (i, j+1)，mask 第 j 位清 0
2. mask 第 j 位 = 0：三種選擇
   • 橫放：佔用 (i,j) 和 (i,j+1) → 要求 j+1 < M 且 mask 第 j+1 位 = 0，遞推 (i, j+2)，mask 這兩位設 1
   • 豎放：佔用 (i,j) 和 (i+1,j) → 遞推 (i, j+1)，mask 第 j 位設 1（標記下行被佔用）
   • （若為最後一行不能豎放）

相容性檢查：當前行狀態 vs 上一行狀態

上一行狀態 prev，當前行狀態 cur：

• prev 第 j 位 = 1 ⇒ 上行有豎磚延伸至此，cur 第 j 位必須為 1（接住磚塊）
• prev 第 j 位 = 0 ⇒ cur 第 j 位可為 0 或 1（視本行放置決定）

完整 AC 程式碼

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000007;
const int MAXN = 1000;
const int MAXM = 1 << 10; // M ≤ 10

int N, M;
long long dp[MAXN][MAXM];

// 檢查第一行狀態合法性（無上行約束）
bool check_first(int mask) {
    for (int i = 0; i < M; ) {
        if (mask & (1 << i)) { i++; continue; } // 豎磚延伸標記（第一行不能有）
        // 橫放：需 i+1 < M 且 mask 第 i+1 位也為 0
        if (i + 1 >= M || (mask & (1 << (i+1)))) return false;
        i += 2;
    }
    return true;
}

// 檢查 prev → cur 相容性
bool check_compat(int prev, int cur) {
    for (int i = 0; i < M; ) {
        if (prev & (1 << i)) {
            // 上行有豎磚，本行必須接住
            if (!(cur & (1 << i))) return false;
            i++;
        } else {
            // 上行無豎磚
            if (cur & (1 << i)) {
                // 本行豎放 → 下行會有延伸標記
                i++;
            } else {
                // 本行橫放 → 需 i+1 也無上行豎磚且本行也橫放
                if (i + 1 >= M || (prev & (1 << (i+1))) || !(cur & (1 << (i+1)))) return false;
                i += 2;
            }
        }
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> N >> M;
    if (M > N) swap(N, M); // 讓 M 為較小維度
    
    int all = 1 << M;
    memset(dp, 0, sizeof(dp));
    
    // 第一行初始化
    for (int s = 0; s < all; s++)
        if (check_first(s)) dp[0][s] = 1;
    
    // 逐行 DP
    for (int i = 1; i < N; i++) {
        for (int cur = 0; cur < all; cur++) {
            for (int prev = 0; prev < all; prev++) {
                if (check_compat(prev, cur)) {
                    dp[i][cur] = (dp[i][cur] + dp[i-1][prev]) % MOD;
                }
            }
        }
    }
    
    // 最後一行狀態必須全為 0（無下行延伸）
    cout << dp[N-1][0] << '\n';
    return 0;
}

關鍵點總結

• 狀態語義：mask 表示「下一行被佔用情況」，而非當前行
• 維度交換：令 M 為較小維度，狀態數 2^M 最小化
• 第一行特殊：不能有豎磚延伸標記（無上行）
• 最後一行約束：答案為 dp[N-1][0]，不能有延伸到虛擬第 N 行的豎磚
• 複雜度：O(N × 4^M)，M≤10 時 4^10=1e6，N=100 共 1e8 邊界可行