宁妄
要解决这个问题，我们需要计算用n个红、黄、蓝三种颜色的珠子排列成一行，满足相邻颜色不同且首尾颜色不同的方案数。我们可以通过动态规划结合数学推导来解决。
问题分析
- 约束条件：相邻颜色不同，且首尾颜色不同。
- 对称性简化：由于三种颜色对称，我们可以固定第一个珠子的颜色（如红色），计算该情况下的合法方案数，最后乘以3（三种颜色选择）。
动态规划思路
定义状态：
B_i：长度为i，首颜色固定为红色，末颜色非红色的合法方案数（相邻颜色不同）。
递推关系：
- 当长度为
i时，末颜色非红的方案数B_i等于总相邻不同的方案数（首红）减去末颜色为红的方案数A_i。 - 总相邻不同的方案数（首红）为
2^(i-1)（第二个珠子有2种选择，之后每个珠子有2种选择）。 - 末颜色为红的方案数
A_i等于长度为i-1时末颜色非红的方案数B_{i-1}（因为第i个珠子要为红，第i-1个珠子必须非红）。
因此，递推式为：Bi=2i−1−Bi−1 B_i = 2^{i-1} – B_{i-1} Bi=2i−1−Bi−1
初始条件：当i=2时，B_2=2（首红，第二个珠子只能是黄或蓝）。
数学推导
通过递推式可推导出通项公式：Bn=2n+2(−1)n3 B_n = \frac{2^n + 2(-1)^n}{3} Bn=32n+2(−1)n
总方案数为三种首颜色的情况之和，即：ans=3×Bn=2n+2(−1)n \text{ans} = 3 \times B_n = 2^n + 2(-1)^n ans=3×Bn=2n+2(−1)n
代码实现
根据通项公式，直接计算即可：
n = int(input())
ans = (2 ** n) + 2 * ((-1) ** n)
print(ans)验证
- 输入样例1（n=2）：22+2×(−1)2=4+2=6 2^2 + 2 \times (-1)^2 = 4 + 2 = 6 22+2×(−1)2=4+2=6，与输出一致。
- 输入样例2（n=3）：23+2×(−1)3=8−2=6 2^3 + 2 \times (-1)^3 = 8 – 2 = 6 23+2×(−1)3=8−2=6，与输出一致。
该方案通过动态规划推导并简化为数学公式，时间复杂度为O(1) O(1) O(1)（直接计算指数），适用于n≤60的所有情况。
