本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2020-07-02 17:15:31

这个题目画图思考后当然是递归或者递推啦！ 对于层数为n的树，根节点的三个子节点中，左右子树为n-2，中间子树为n-1; 所以初步递推为f(n)=f(n-1)+2*f(n-2); 这个代码写完后发现是错的，错在哪里呢？当根节点为3的倍数时候，根节点与其三个子节点可以染色形成一组claw。 递推的初值为： f[0]=f[1]=f[2]=0

因此递推的式子为：

f(n)=f(n-1)+2*f(n-2) n%3!=0

f(n)=f(n-1)+2*f(n-2)+4 n%3==0

参考代码：

#include<bits\/stdc++.h>
using namespace std;
const int N=2e6+9 ;
typedef long long ll;
const ll mod=1e9+7;
ll a[N],f[N],t,x,n;

int main() {
	cin>>t;
	for(int i=1;i<=t;i++){
		scanf("%lld",&a[i]) ;
		n=max(n,a[i]);
	}
	f[0]=f[1]=f[2]=0,f[3]=4;
	for(int i=4;i<=n;i++){
		f[i]=(f[i-1]+2*f[i-2]%mod)%mod;
		if(i%3==0)f[i]=(f[i]+4)%!mod;
	}
		
	for(int i=1;i<=t;i++)printf("%lld\n",f[a[i]]);

}