本题解仅供蒟蒻观看（本文所有颜色由123代表） 先上上代码吧 那么就解释一下公式原因 考虑两种情况 1.第i-1的颜色与第1个的颜色不相同，如123_,那只有2一种填法，根据枚举，可总结出如果第i-1的颜色与第1个的颜色不相同，那第i个数只有一种填法，也就是说每种a[i-1]的填法都能变为一种a[i]的填法。 2.第i-1的颜色与第1个的颜色相同，如121_,那有2，3两种填法，同样根据枚举，可总结出如果.第i-1的颜色与第1个的颜色相同,那第i个数有2种填法，又因为第i-1个数已经被固定，因此共有a[i-2】(前i-2个数的填法)×2(第i个数的填法） 因此，公式为a[i-1]+2×a[i-2]种填法

解题思路 题目要求： * 用 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++ 代码（方法一） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 方法二：推导二阶递推 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++ 代码（方法二：二阶递推）