题解 | #舔狗舔到最后一无所有#

因为连续三天不能去同一家外卖； 那么，设三家外卖的序号为0,1,2；

假设第i天去了第j家，则：

1：第i-1天没去第J家，那就不会三天吃同一家，也就是第i-1天 可以去另外两家；

2：第i-1天去了第J家，那么因为三天不能吃同一家，那第i-2天就只能去另外两面；

以第i天去了第0家为例：

dp[i][0]+=(dp[i-1][1]+dp[i-1][2])%mod;第i-1天不去第0家；

dp[i][0]+=(dp[i-2][1]+dp[i-2][2])%mod;第i-1天去了第0家；

using namespace std;
const int N=1e6+5,mod=1e9+7;
#define ll long long 
ll dp[N][5];
int main()
{
    int i,j;
	dp[1][0]=1,dp[1][1]=1,dp[1][2]=1;
    dp[2][0]=3,dp[2][1]=3,dp[2][2]=3;
//dp[i][j]第i天去第j家；
    for(i=3;i<=1e5+5;i++){
        dp[i][0]=(dp[i-1][1]+dp[i-1][2]+dp[i-2][1]+dp[i-2][2])%mod;
        dp[i][1]=(dp[i-1][0]+dp[i-1][2]+dp[i-2][0]+dp[i-2][2])%mod;
        dp[i][2]=(dp[i-1][0]+dp[i-1][1]+dp[i-2][0]+dp[i-2][1])%mod;
    }
    int t;cin>>t;
    while(t--){
        int n;scanf("%d",&n);
        int ans=(dp[n][0]+dp[n][1]+dp[n][2])%mod;
        printf("%lld\n",ans);
    }
    return 0;
}