最暴力的一集

反正就是枚举每一个状态，$dp[i][j][k]$ 表示当前是第 $i$ 个方格，首个方格填 $j$，这个方格填 $k$ 的方案数

#include <iostream>
#include <cstdio>
#define int long long
using namespace std;
const int mod = 998244353;
int dp[200005][3][3];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	for(int i = 0; i <= 2; i++){
		dp[1][i][i] = 1;
	}
	for(int i = 2; i < n; i++){
		for(int j = 0; j <= 2; j++){
			for(int k = 0; k <= 2; k++){
				for(int l = max(k - 1, 0ll); l <= min(k + 1, 2ll); l++){
					dp[i][j][k] += dp[i - 1][j][l];
				}
				dp[i][j][k] %= mod;
			}
		}
	}
	int ans = 0;
	for(int i = 0; i <= 2; i++){
		for(int j = 0; j <= 2; j++){
			for(int k = 0; k <= 2; k++){
				if(abs(i - k) <= 1 && abs(j - k) <= 1){
					ans += dp[n - 1][i][j];
				}
			}
		}
	} 
	cout << ans % mod;
	
	return 0;
}

时间复杂度 $O(nm^3)$，其中 $m=2$