藍橋杯「格子刷油漆」題目解題思路：排除法 + 動態規劃推導完整解析

題目重述

2×N 格子，從任一格開始，每步移至相鄰格（含對角），不可重複踩格，求完整走完所有格的路徑數，模 1,000,000,007。

核心觀察：唯一的非法情況

若某一列的兩格**都已刷完**，而**左側仍有未刷格子**，則無法返回左側完成遍歷 → 此路徑無效。

狀態定義與遞推

逐列掃描，定義狀態：

• dp[i][0]：第 i 列結束時，兩格皆未刷（不可能，因需連續）。
• dp[i][1]：第 i 列僅上格刷完，下格未刷（或對稱）。
• dp[i][2]：第 i 列兩格皆刷完，且**左側無遺漏**（合法狀態）。

經推導得到遞推關係（詳見官方解析），最終可化為線性遞推：

f[n] = 4*f[n-1] + 2*f[n-2]   (n>=3)
f[1]=2, f[2]=24

矩陣快速冪優化 (O(log N))

[f[n]  ]   [4 2] [f[n-1]]
[f[n-1]] = [1 0] [f[n-2]]

配合模運算，N ≤ 1000 瞬時求解。

驗證樣例

參考資源

藍橋杯官方題解、乙級真題分析博客。