链接：https://ac.nowcoder.com/acm/contest/24213/1002 来源：牛客网

作为队伍的核心，forever97很受另外两个队友的尊敬。 Trote_w每天都要请forever97吃外卖，但很不幸的是宇宙中心forever97所在的学校周围只有3家forever97爱吃的外卖。 如果Trote_w给forever97买了别家的外卖，forever97就会大喊“我不吃我不吃”。 但是forever97又不喜欢连续三天吃一种外卖。 如果Trote_w哪天忘了这件事并且三天给他买了同一家外卖，那么forever97就会把Trote_w的头摁进手机屏幕里。 作为Trote_w的好朋友，你能告诉他连续请forever97吃n天饭，有多少不同的购买方法吗？

题目解析

其实可以理解为 a b c三个字母排列，不能有连续三个字母排在一起

可以定义两个数组，一个是最后两个字母相同的t[i],一个是最后两个字母是不同的bt[i]

扩散的视角：

1、t[i]后面只能跟另外两个字母且肯定不同，所以扩散到bt[i+1]的部分是t[i]*2

2、bt[i]后面可以跟任意字母，但是要有所区分，其中有一个相同，两个不相同，所以扩散到t[i+1]一份，扩散到bt[i+1]两份

可得递推公式为：

bt[i] = (bt[i-1] + t[i-1])*2;
t[i] = bt[i-1];

在计算的过程中进行模运算即可，最后输出的是同和不同的加起来的结果，完整代码如下：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9+7;
void slove(){
    int n;
    cin >> n;
    vector<int> t(n+1),bt(n+1);
    t[1] = 0;
    bt[1] = 3;
    for(int i=2;i<=n;i++){
        bt[i] =( t[i-1]*2 + bt[i-1]*2) % MOD;
        t[i] = bt[i-1] % MOD;
    }
    cout << (t[n] + bt[n])%MOD << endl;
    return ;
}
signed main() {
    int T;
    cin >> T;
    while(T--) slove();
    return 0;
}