解題說明
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 正方形骨牌，方法數如何改變？