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

題目大意

用 3 種顏色給 n 個環狀排列的格子染色，相鄰格子顏色不同，首尾也相鄰。求合法染色方案數。n ≤ 50。

遞推關係推導

設 f[n] 為長度 n 環的合法方案數。考慮第 n 個格子：

1. 若前 n-1 個格子已合法（首尾不同），第 n 格只能選第 1 格和第 n-1 格都不是的顏色 → 1 種選法。貢獻：f[n-1]。
2. 若前 n-1 個格子不合法（首尾相同），加上第 n 格後變合法。這要求前 n-2 個格子合法，且第 n-1 格與第 1 格同色。此時第 n 格可選除該顏色外的 2 種。貢獻：2 * f[n-2]。

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

代碼實現

#include <stdio.h>

int main() {
    long long f[55];
    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 (~scanf("%d", &n)) printf("%lld\n", f[n]);
    return 0;
}

驗證

• n=1：3 種
• n=2：3*2=6 種
• n=3：3*2*1=6 種（三角形三色適度染色）
• n=4：6 + 2*6 = 18

結果為整數序列，n=50 時約 2.5e15，需 long long（__int64）。