HDU 2045 LELE的RPG難題：環狀三色著色遞推公式推導

題目重述

n 個方塊排成一環（首尾相連），用紅/粉/綠三色著色，相鄰不同色（含首尾）。求合法著色方案數。n ≤ 50，多測試用例。

遞推關係推導

設 f[n] 為 n 環合法方案數。考慮第 n 個方塊與第 1 個的關係：

• 情況 1：第 n-1 與第 1 色不同
  則第 n 個只能選「不同於 n-1 且不同於 1」的唯一顏色。
  這等價於 n-1 個方塊排成一環的合法方案 → f[n-1] 種。
• 情況 2：第 n-1 與第 1 色相同
  則第 n 個可選「不同於 n-1」的兩種顏色（自動滿足首尾不同）。
  前 n-2 個方塊排成一環，第 n-1 強制等於第 1 → 等價於 n-2 環方案，每種衍生 2 種 → 2×f[n-2] 種。

合併得遞推式：

f[n] = f[n-1] + 2*f[n-2]   (n ≥ 4)
f[1] = 3, f[2] = 6, f[3] = 6

驗證小值

• n=1：3 色任選 → 3
• n=2：首尾相鄰，順序有關 → 3×2 = 6
• n=3：三角環，全排列 → 3×2×1 = 6
• n=4：f[4] = 6 + 2×6 = 18 ✓

完整代碼（預計算 + O(1) 查詢）

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    vector<int64> f(51);
    f[1]=3; f[2]=6; f[3]=6;
    for(int i=4;i<=50;i++) f[i] = f[i-1] + 2*f[i-2];
    
    int n;
    while(cin >> n) {
        cout << f[n] << "\n";
    }
    return 0;
}

數學本質：特徵方程求通項

x² - x - 2 = 0 → 根 x₁=2, x₂=-1
通項：f[n] = A·2ⁿ + B·(-1)ⁿ
代入初值解得 A=1, B=1 → f[n] = 2ⁿ + (-1)ⁿ

驗證：n=1: 2-1=1？等等，f[1]=3... 實際通項為 f[n] = 2ⁿ + 2·(-1)ⁿ？
重新解：
f[1]=3: 2A - B = 3
f[2]=6: 4A + B = 6
解得 A=1.5, B=0 → 不對。
正確特徵方程對應遞推 f[n]=f[n-1]+2f[n-2]：
λ² - λ - 2 = 0 → λ=2, -1
f[n] = α·2ⁿ + β·(-1)ⁿ
n=1: 2α - β = 3
n=2: 4α + β = 6
→ 6α = 9 → α=1.5, β=0 → f[n]=1.5×2ⁿ 非整數...
錯誤：遞推從 n≥4 開始，f[3] 不滿足該遞推！
實際 f[3]=6，但遞推給出 f[3]=f[2]+2f[1]=6+6=12。
所以 f[1..3] 是基本情況，n≥4 才遞推。通項公式較繁瑣，預計算最簡潔。

總結

• 環狀著色 → 討論倒數第二與第一的關係 → 遞推 f[n]=f[n-1]+2f[n-2]
• n≤50 直接預計算 long long 即可，無需矩陣快速冪
• 注意 f[3]=6 不滿足遞推，為基本情況之一