• 开2个数组

1. a[]表示在2*N的格子,从四个顶点中任意一个格子出发遍历全部格子的种类数,a[1] = 1 a[2] = 6(画出所有情况)
2. b[]表示在2*N的格子,从任意一个格子出发,遍历所有格子且终点在出发点这一列,以为要回来,所有每一步只能一直往左或者右走(这样该列另一个格子就会留个回来时刷),所以每一步2中选择,b[i] = 2 * b[i-1]

• 出发点在四个顶点处,考虑a[],有3中走法,

1. 先去该列的另一个,那么下一列有2种 选择, a[i] += 2 * a[i-1],
2. 终点是该列另一个格子,a[i] += b[i],走的是b[]的方法
3. 这一种是先去下一列(第二列),然后将第三列的两个格子都刷完,去第二列有2个格子可以选,位于第二列时去第三列也有2个格子可以选,所以a[i] += 4 * a[i-1]

• 结果sum是从四个点出发+中间列的任一点出发所得到的路径总数

1. 出发点在中间时,无论先遍历左边还是右边都要 通过出发点的列的另一个点 到达左(右)边
2. 所以 任意一列中选择出发点有2中选择,先遍历 左所有点且回到 出发点这一列另一个点 方法为b[i],然后遍历右边(终点任意),且出发点在该列右边一列任意选择2个点,则方法为为2 * a[n-i]
3. 同理先遍历右边也是这样
   $sum = 4b[n] + \Sigma_{i=2}^{N-1} (22b[i]a[n-i] + 22b[n-i+1] * a[i-1])$

• 公式左边是先遍历左边,右边是先遍历右边,画图注意先遍历右边的索引问题

  #include <iostream>
  #define MOD 1000000007
  using namespace std;
  const int maxn = 1e3+5;
  long long a[maxn];
  long long b[maxn];
  int n;
  int main() {
  	cin >> n;
  	b[1] = 1;
  	for (int i=2; i<=n; i++) 
  		b[i] = (b[i-1] * 2 % MOD);
  	a[1] = 1;
  	a[2] = 6; //
  	for (int i=3; i<=n; i++) 
  		a[i] = ( 2*a[i-1] + b[i] + 4*a[i-2] ) % MOD;
  	long long sum = (4*a[n])%MOD;
  	for (int i=2; i<n; i++) {
  		sum = (sum + (4 * b[i] * a[n-i])%MOD + (4 * b[n-i+1] * a[i-1])%MOD) % MOD;
  	}
  	if (n == 1) sum = 2;
  	cout << sum;
  	return 0;
  }