[数据结构与算法]This is an interesting introduction DP!

结论：

知识点：动态规划–递推

转移方程：$dp[i+1][0]=4?dp[i][0]+dp[i][1]$

? $dp[i+1][1]=dp[i][0]+2?dp[i][1]$

结论：$ans=(dp[n][0]+dp[n][1])\%mod$

转移方程解释：

$dp[i][0]$ 表示$i$层的大矩阵最后一层以 |_|_| 这种形式（即两个格子之间有间隔）时，拼成大矩阵有多少种方案数

$dp[i][1]$ 表示$i$层的大矩阵最后一层以 |____| 这种形式（即两个格子之间不存在间隔）时，拼成大矩阵有多少方案数

结论推导：

从上面图片可以看出：

如果第$i$层有$x$个情况一，$y$个情况二，那么第$i+1$层情况一：$4?x(i层情况一贡献)+y(i层情况二贡献)$,情况二：$x(i层情况一贡献)+2?y(i层情况二贡献)$

从而得到我们的转移方程

$dp[i+1][0]=4?dp[i][0]+dp[i][1]$

$dp[i+1][1]=dp[i][0]+2?dp[i][1]$

而一层中情况一和情况二的总数才是要求的总方案数

$\therefore ans=dp[n][0]+dp[n][1]$

Code

# python
if __name__ == '__main__':
    DP = [[0] * 2 for i in range(1000010 + 1)]
    # 初始化边界 n==1的时候，第一种情况和第二种情况都只有一种
    DP[0][0] = 1
    DP[0][1] = 1
    mod = int(1e9 + 7)
    for i in range(1, 1000005):
        # 转移方程
        DP[i][0] = (4 * DP[i - 1][0] + DP[i - 1][1]) % mod
        DP[i][1] = (DP[i - 1][0] + 2 * DP[i - 1][1]) % mod
    while True:
        try:
            T = int(input())
            while T > 0:
                T -= 1
                n = int(input())
   
                ans = DP[n - 1][0] + DP[n - 1][1]
                print(ans % mod)

        except EOFError:
            break

//C++
#define _CRT_SECURE_NO_WARNINGS

#include<bits/stdc++.h>
using namespace std;

#define ll long long
const ll maxn = 1e6 + 10;
const ll mod = 1e9 + 7;
ll dp[maxn][2];
signed main()
{
#ifndef ONLINE_JUDGE
	freopen("1.in", "r", stdin);
	freopen("1.out", "w", stdout);
#endif
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	// 初始化边界 n==1的时候，第一种情况和第二种情况都只有一种
	dp[1][0] = 1;
	dp[1][1] = 1;
	// 转移方程
	for (int i = 2; i <= maxn-5; i++) {
		dp[i][0] = (4 * dp[i - 1][0] + dp[i - 1][1]) % mod;
		dp[i][1] = (dp[i - 1][0] + 2 * dp[i - 1][1]) % mod;
	}
	ll T;
	cin >> T;
	while (T--) {
		ll n;
		cin >> n;
		
		cout << (dp[n][0] + dp[n][1]) % mod << "\n";
	}

	return 0;

}