【题解】【上海】【圆环三染色】

解析：
    第1个点3种颜色可以任意选，a[1]=3
    第 2~n-1 个点，每个点都有 2 种颜色可选，a[i]=2; (1<i<n)
	第 n 个点：如果 a[1]==a[n-1], a[n]=2;
			  如果 a[1]!=a[n-1], a[n]=1;
那么1到n-1共有多少可能？
    		 ----因为1的颜色==n-1的颜色，所以1的颜色！=n-2的颜色，所有共有f(n)种可能，再乘上第n个的可能，共有2*f(n-2)可能。
    			1的颜色!=第n-1的颜色，那么第n个只有1种可能。1到n-1共有f(n-1)种可能，再乘上第n个的可能，共有f(n-1)的可能。
   				公式： f(n)=2∗f(n−2)+f(n−1)
    用数组的话，需要开的数组太大了，无法创建
    60分代码：
#include <bits/stdc++.h> 
using namespace std;  
long long M = 1000000007;
int main()
{
	long long n, a,b,c;
	cin>>n;
	if(n==1) {
		cout<<3;
		return 0;
	}
	if(n==2 || n==3){
		cout<<6;
		return 0;
	}
//初始化
	a = 6, b=6;
	for(int i=4; i<=n; i++){
		c = (2*a+b)%M;
		a = b;
		b = c;
	}
	cout<<c;
    return 0;
}