HDU 2045 LELE 的 RPG 難題：三色環狀塗色遞推規律與大數處理

問題重述

有 n (0 < n ≤ 50) 個方格排成一環，用紅、粉、綠三色塗色，滿足：

1. 相鄰方格顏色不同。
2. 首尾方格顏色不同（環狀）。
3. 求合法塗法總數。

遞推關係推導

設 f[n] 為 n 個方格環的合法塗法數。考慮從 n-1 擴展到 n：

• 若第 n-1 個方格與第 1 個方格顏色不同，新加入的第 n 個方格只能填第 3 種顏色（1 種選擇）。
• 若第 n-1 個方格與第 1 個方格顏色相同，新方格可填除該顏色外的 2 種（2 種選擇）。

觀察發現：n-1 首尾同色 ⇔ n-2 首尾不同色（合法）。故：

f[n] = f[n-1] × 1 + f[n-2] × 2

初始值：f[1]=3, f[2]=6, f[3]=6（可手動驗證）。

遞推表 (n=1..10)

Java 大數實現 (BigInteger)

f[50] 超過 64 位整數範圍，需用 BigInteger 或 Java long 實測 f[50] ≈ 2.8e15 仍在 long 範圍內（9e18），但為保險建議用 BigInteger。

import java.math.BigInteger;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        BigInteger[] f = new BigInteger[51];
        f[1] = BigInteger.valueOf(3);
        f[2] = f[3] = BigInteger.valueOf(6);
        for (int i = 4; i <= 50; i++)
            f[i] = f[i-1].add(f[i-2].multiply(BigInteger.valueOf(2)));
        while (sc.hasNext()) {
            int n = sc.nextInt();
            System.out.println(f[n]);
        }
    }
}

C++ 長整型實現

long long 足夠（f[50] = 281474976710658 < 9e18）。

#include <cstdio>
#include <iostream>
using namespace std;
long long f[51];
int main() {
    f[1]=3; f[2]=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] = f[n-1] + 2*f[n-2] 形式簡單，屬於線性遞推，可用矩陣快速冪優化至 O(log n)，但 n≤50 直接 DP 即可。
注意 n=1,2,3 的基礎情況手動驗證，避免邊界錯誤。