$O(3 * 3 *n)$ DP做法

1. 互质

题目给定数字1,5,6，只有当5, 5 和6，6相邻时才有不互质的情况。即只要 $5$ 旁边不放 $5$, $6$周围不放$6$即可

2. DP计算方案

• 状态设计：$dp[i][j][k]$ 为第 $i$ 列第一行取 $j$ 第二行取 $k$ 的方案数。后两维的数字用 $1,2,3$ 来表示 $1,5,6$ 。
• 状态转移：对于第i列的状态，将 $i-1$ 列所有合法状态求和。合法的意思是没有 $5$和 $6$ 相邻.

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int mod=1e9+7;
typedef long long ll;
ll dp[N][5][5];
int n;
void calc(int id,int a,int b){
	if(a==b&&b!=1){
		return;
	}
	if(a==1&&b==1){
		for(int i=1;i<=3;i++){
			for(int j=1;j<=3;j++){
				dp[id][a][b]=(dp[id][a][b]+dp[id-1][i][j])%mod;
			}
		}
		return;
	}
	dp[id][a][b]=(dp[id][a][b]+dp[id-1][1][1]+dp[id-1][b][a])%mod;
	if(a==1&&b==2){
		dp[id][a][b]=(dp[id][a][b]+dp[id-1][1][3]+dp[id-1][3][1]+dp[id-1][2][3])%mod;
	}
	if(a==2&&b==1){
		dp[id][a][b]=(dp[id][a][b]+dp[id-1][1][3]+dp[id-1][3][1]+dp[id-1][3][2])%mod;
	}
	if(a==1&&b==3){
		dp[id][a][b]=(dp[id][a][b]+dp[id-1][1][2]+dp[id-1][2][1]+dp[id-1][3][2])%mod;
	}
	if(a==3&&b==1){
		dp[id][a][b]=(dp[id][a][b]+dp[id-1][1][2]+dp[id-1][2][1]+dp[id-1][2][3])%mod;
	}
	if(a==2&&b==3){
		dp[id][a][b]=(dp[id][a][b]+dp[id-1][1][2]+dp[id-1][3][1])%mod;
	}
	if(a==3&&b==2){
		dp[id][a][b]=(dp[id][a][b]+dp[id-1][1][3]+dp[id-1][2][1])%mod;
	}
	
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	cin>>n;
	dp[1][1][2]=dp[1][2][1]=dp[1][1][3]
	=dp[1][3][1]=dp[1][2][3]=dp[1][3][2]=dp[1][1][1]=1;
	for(int i=2;i<=n;i++){
		for(int j=1;j<=3;j++){
			for(int k=1;k<=3;k++){
				calc(i,j,k);
			}
		}
	}
	ll ans=0;
	for(int i=1;i<=3;i++){
		for(int j=1;j<=3;j++){
			ans=(ans+dp[n][i][j])%mod;
		}
	}
	cout<<ans;
}