T8:Gold King上色

解题思路

题目要求：

• 用 3 种颜色给一排 n 个格子涂色
• 相邻格子颜色不同
• 头尾颜色也不同（相当于把第 1 个格子和第 n 个格子也当作相邻）
• 特别地：n = 1 时“头也是尾”，要求头尾不同无法满足，所以答案是 0

这其实就是长度为 n 的环（cycle）的 3-染色方案数。

---

方法一：分类 DP（固定第 1 格颜色）

把第 1 个格子颜色固定为某一种（例如颜色 A）。由于颜色对称，最后乘 3 即可。

固定第 1 格后，考虑从第 2 格到第 n 格的涂法，并且最后还要满足第 n 格 ≠ 第 1 格（不能是 A）。

设：

• same[i]：涂到第 i 格时，第 i 格颜色 等于第 1 格(A) 的方案数
• diff[i]：涂到第 i 格时，第 i 格颜色 不等于 A 的方案数

初始化（第 1 格是 A）：

• same[1] = 1
• diff[1] = 0

转移（相邻不同）：

• 从 same[i-1] 到第 i 格：第 i 格不能是 A，只能是另外 2 种

  diff[i] += same[i-1] * 2

• 从 diff[i-1] 到第 i 格：

  • 选 A：1 种 → same[i] += diff[i-1] * 1
  • 选另一个非 A 且与上一个不同：1 种 → diff[i] += diff[i-1] * 1

所以：

• same[i] = diff[i-1]
• diff[i] = 2 * same[i-1] + diff[i-1]

最终（固定第 1 格为 A）合法方案数是 diff[n]（因为第 n 格必须 ≠ A）。

总答案：

• ans = 3 * diff[n]

并且：

• n = 1 输出 0

---

C++ 代码（方法一）

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

long long same_[55], diff_[55];

int main() {
    int n;
    cin >> n;

    if (n == 1) {
        cout << 0 << endl;
        return 0;
    }

    // 固定第1格为颜色A
    same_[1] = 1;
    diff_[1] = 0;

    for (int i = 2; i <= n; i++) {
        same_[i] = diff_[i - 1];
        diff_[i] = 2 * same_[i - 1] + diff_[i - 1];
    }

    long long ans = 3 * diff_[n];
    cout << ans << endl;
    return 0;
}

---

方法二：推导二阶递推 a[n] = a[n-1] + 2*a[n-2]

1）先把问题翻译成“环染色”

• 有 n 个格子排成一圈（因为要求“头尾颜色也不同”，等价于第 1 个和第 n 个也相邻）
• 颜色有 3 种（记为 0、1、2）
• 约束：每条相邻边两端颜色不同

这就是长度为 n 的环 Cₙ 的 3-染色计数。

2）为什么 a[1]=0，a[2]=6

• n = 1：只有一个格子，它既是头又是尾，还要求头尾不同，这是不可能的

  所以 a[1] = 0。

• n = 2：两个格子互为相邻，同时也满足“头尾不同”（其实就是这两个不同）

  第一个格子 3 种选法，第二个格子必须不同于第一个，有 2 种

  所以 a[2] = 3 * 2 = 6。

3）关键：推导递推式 a[n] = a[n-1] + 2*a[n-2]

为了推递推，先固定第 1 个格子的颜色为 A。由于三种颜色对称，最后乘 3 就能得到总数。

令：

• b[n] = 在“第 1 格固定为 A”的前提下，满足条件的涂法数（仍需满足：第 n 格 ≠ A）

显然：

• a[n] = 3 * b[n]

更直接的做法：用“最后一格是否等于 A”来做两状态 DP，然后消元得到二阶递推。

4）用两状态 DP 推到二阶递推（最清晰）

仍然固定第 1 格为 A。

定义：

• S[i]：走到第 i 格时，第 i 格 等于 A 的方案数
• D[i]：走到第 i 格时，第 i 格 不等于 A 的方案数

初始：

• S[1] = 1（第 1 格就是 A）
• D[1] = 0

转移（相邻不同）：

1. 要让第 i 格等于 A：

   第 i-1 格必须不等于 A

   S[i] = D[i-1]

2. 要让第 i 格不等于 A：

   • 若第 i-1 格等于 A：第 i 格可选另外两种颜色（2 种）

   • 若第 i-1 格不等于 A：第 i 格可选的“不等于 A 且不等于第 i-1 格”的颜色只有 1 种

     所以：

     D[i] = 2 * S[i-1] + 1 * D[i-1]

最终要满足环条件：第 n 格 ≠ A，因此：

• b[n] = D[n]
• a[n] = 3 * D[n]

现在把 D 的递推化成二阶形式。由 S[i] = D[i-1] 代入：

• D[i] = 2 * D[i-2] + D[i-1]
• 即 D[i] = D[i-1] + 2 * D[i-2]

两边乘 3：

• a[i] = a[i-1] + 2 * a[i-2]

并且：

• D[1] = 0 ⇒ a[1] = 0
• D[2] = 2 ⇒ a[2] = 3 * 2 = 6

5）对拍样例 n=4

• a[1] = 0
• a[2] = 6
• a[3] = a[2] + 2*a[1] = 6
• a[4] = a[3] + 2*a[2] = 6 + 12 = 18

符合样例输出 18。

---

C++ 代码（方法二：二阶递推）

#include <iostream>
using namespace std;

long long a[114514];

int main() {
    int n;
    cin >> n;

    a[1] = 0;
    a[2] = 6;

    for (int i = 3; i <= n; i++) {
        a[i] = a[i - 1] + 2 * a[i - 2];
    }

    cout << a[n] << endl;
    return 0;
}