环形着色问题

用三种颜色对n个石头着色，相邻不同色，首尾不同色，一共几种方法

第一步：只考虑相邻不同色(不考虑首尾不同色)，则方法数为：3*2*2*...*2，即：$3*2^{n-1}$

第二步：加上“首尾不同色”的限制（变成环形）
刚刚的情形其实包含了两种情况：
情况1、第1个和第n个颜色不同（这正是我们想要的）。
情况2、第1个和第n个颜色相同（这是需要剔除的）。

设f(n)为n个石头围成一圈且满足条件的着色方法数（即情况 1 的数量）。
对于情况2(首尾颜色相同)，我们可以把第1个和第n个石头看作粘在一起变成了1个石头。
加上 相邻不同色 的要求，则即 第1个 和 倒数第2个(看作新的最后一个) 不同色，
则 情况2 等价于 求解：n-1个石头围成一圈且满足条件的着色方法数（f(n-1)）

结合以上，有 f(n)+f(n-1)=$3*2^{n-1}$，即 f(n)=$3*2^{n-1}$-f(n-1)，有递推公式了
当 n=1 时，自己和自己冲突，0 种。

#include<bits/stdc++.h>
using namespace std;
int main() {
	long long n, a[51]={0, 0};
	cin>>n;
	for(int i=2; i<=n; i++) a[i]=3*(1LL<<(i-1))-a[i-1]; //这里利用位运算求解2的某次方
	cout<<a[n];
	return 0;
}