BNU 條形碼設計：遞推與對稱性計數

問題描述

2×n 的矩形，用 2×1 豎放、1×2 橫放（兩個疊起）、2×2 方塊鋪滿。鋪法視為條形碼。求本質不同（考慮鏡像對稱）的鋪法數。n ≤ 28。

不考慮對稱的遞推

考慮最左側：

• 放一個豎條（2×1）→ 剩餘 2×(n-1)：f[n-1] 種。
• 放兩個橫條（上下各 1×2）→ 剩餘 2×(n-2)：f[n-2] 種。
• 放一個 2×2 方塊 → 剩餘 2×(n-2)：f[n-2] 種。

遞推：f[n] = f[n-1] + 2*f[n-2]，f[1]=1, f[2]=3。

對稱鋪法計數

對稱軸在中間。分 n 奇偶：

• n 奇：中間必須是一條豎條。左側 2×(n-1)/2 任意鋪法：s[n] = f[(n-1)/2]。
• n 偶：中間無豎條。左側 2×(n/2) 任意鋪法，或左側 2×(n/2-1) 加中間兩橫條/一塊 2×2：s[n] = f[n/2] + 2*f[n/2-1]。

本質不同總數

總數 = (非對稱數 × 2 + 對稱數) / 2 = (f[n] + s[n]) / 2。

代碼實現

#include 
using namespace std;

int main() {
    vector f(29), s(29);
    f[1]=1; f[2]=3; s[1]=1; s[2]=3;
    for (int i = 3; i <= 28; i++) {
        f[i] = f[i-1] + 2*f[i-2];
        if (i & 1) s[i] = f[i/2];
        else s[i] = f[i/2] + 2*f[i/2-1];
    }
    int n, tc = 1;
    while (cin >> n, n) {
        cout << "Case " << tc++ << ": " << (f[n] + s[n]) / 2 << "\n";
    }
    return 0;
}

複雜度

• 預處理 O(28)，查詢 O(1)。

總結

本題展示了「先算總數，再算對稱數，最後去重」的組合計數套路。關鍵在於正確分析對稱結構的中間形式（奇偶不同），並建立對稱數與總數的遞推關係。