G 爱女装的社长
题目大意：
n个位置排成一列，每个位置可以填1,2,3，要求不能有连续三个位置填相同的数，求方案数
\(n<=10^5\)
算法思路
看完题，似乎是个数学题？不太会
不急，观察数据范围，或许可以想一种稍微慢一点的办法
考虑DP
先谈一谈个人对DP的理解：DP，其实利用的是无后效性的特点，把对之前处理完的所有数据，进行一定的归纳，再集中处理。
比如在此题中，若是没有“要求不能有连续三个位置相同”的限制，答案是什么？
毫无疑问\(3^n\)!!!,其实在这个过程中就运用到了无后效性的特点:每个位置都有三种选择,若是没有限制,则每个位置之间互不影响,所以可以对每个位置进行相似的计算
那么我们再回到原题目,现在有了限制.
若还是从前往后填那么每个位置填数时的选择就会被前两个数影响,即:前两个数产生了后效性。
如何消除后效性呢？
我们采取枚举+记录的办法即可，也是动态规划题的通用套路：把后效性的部分记为状态
观察到1,2，3三种数字其实是等价的，不妨设：\(f_{i,1/2}\) 表示第i个位置末尾连续的数字已经有 \(1 or 2\)个连续的相同数字
那么递推式有：
\[f_{i,1}=f_{i-1,1}*2+f_{i-1,2}*2
\]
\[f_{i,2}=f_{i-1,1}
\]
代码
/*********************************************************************
WRITER:YZHX
DATE:2023.9.12
*********************************************************************/
#include <bits/stdc++.h>
using namespace std;
#define re register
#define in inline
#define ll long long
#define get getchar()
#define db double
in int read() {
int t = 0, x = 1;
char ch = get;
while ((ch < '0' || ch > '9') && ch != '-')
ch = get;
if (ch == '-')
ch = get, x = -1;
while (ch <= '9' && ch >= '0')
t = t * 10 + ch - '0', ch = get;
return t * x;
}
const int mod = 1e9 + 7;
ll f[100100][3];
in void pre() {
int n = 100000;
f[1][1] = 3;
for (re int i = 2; i <= n; ++i)
{
f[i][1] = (f[i - 1][1] * 2 % mod + f[i - 1][2] * 2 % mod) % mod;
f[i][2] = f[i - 1][1];
}
}
int main() {
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
int T = read();
pre();
while (T--) {
int n = read();
cout << (f[n][1] + f[n][2]) % mod << endl;
}
return 0;
}