解題說明
Domino and Tromino Tiling
題目描述:用 1×2 的多米諾骨牌和 L 形三格牌(Tromino)來鋪滿 2×n 的棋盤,求鋪法總數(答案取模 10^9+7)。
解題思路:定義 dp[i] 為鋪滿 2×i 棋盤的方法數,輔助狀態 partial[i] 表示前 i-1 欄完整、第 i 欄只有一格被覆蓋的方法數(上或下各算一種,合計)。
遞推關係:
partial[i] = 2 * dp[i-2] + partial[i-1](從 i-2 完整狀態放一個 L 形牌,有兩種朝向;或從 partial[i-1] 放一個 1×2 豎牌)dp[i] = dp[i-1] + dp[i-2] + partial[i-1](豎放骨牌、橫放兩個骨牌、或用 L 形牌補全 partial 狀態)
此題的關鍵在於正確定義「半完成」的狀態,一旦狀態定義清晰,遞推即可自然推導出來。
C++ 解法
複雜度分析
時間複雜度:O(n) — 單層迴圈從 3 到 n。
空間複雜度:O(n) — 儲存 dp 和 partial 陣列;可優化至 O(1) 只保留前幾個狀態。
虛擬碼
1. Handle base cases: n=1 -> 1, n=2 -> 2 2. Initialize dp[0]=1, dp[1]=1, dp[2]=2, partial[2]=2 3. For i from 3 to n: a. partial[i] = (2 * dp[i-2] + partial[i-1]) % MOD b. dp[i] = (dp[i-1] + dp[i-2] + partial[i-1]) % MOD 4. Return dp[n]
其他解法
矩陣快速冪:將遞推關係寫成矩陣乘法形式,用快速冪在 O(log n) 時間求解。當 n 極大時(例如 10^18)是唯一可行方案,但本題 n ≤ 1000,O(n) 已足夠。
封閉公式:本題有已知的封閉式公式,但涉及複數或高精度計算,競賽中不實用。
延伸思考
- 若棋盤改為 3×n,遞推關係應如何重新定義?
- 此題的矩陣快速冪解法如何建立轉移矩陣?
- 若同時加入 2×2 正方形骨牌,方法數如何改變?