题意：
给出一个2*n的方格，当刷完某一个方格的漆后可以且只可以走到相邻的任何一格，即上 下 左 右 左上 左下 右上 右下。可以从任意一个格子开始刷墙，问有多少种刷法，因为随着n的增大方案数会变多，因此输出方案数mod 1000000007.
思路：
dp[][2], dp[i][0]表示2*i的格子从第i列开始刷，最后回到该格子下面
dp[i][1]表示2*i的格子从第i列开始刷，最后无法回到该格子下面
状态转移方程是：dp[i][0] = 2*dp[i-1][0] 即 A1->B1->...->B2->A2, A1->B2->...->B1->A2, A2也一样
dp[i][1] = 2*(dp[i-1][0]+dp[i-1][1]) + 4*(dp[i-2][0]+dp[i-2][1])
因为不能回到那一端，所以 一种情况是 1- >2 然后是dp1[i-1]+dp2[i-1]，或者2->1 dp1[i-1]+dp2[i-1]，所以乘以2。
或者可以1->3->2->4，1->4->2->3，2->3->1->4，2->4->1->3，所以乘以4。
初始状态：dp[0][0] = 1, dp[0][1] = 0, dp[1][0] = 2, dp[1][1] = 0;
没有格子的情况下每个子涂所以回到该列只有一种情况，而回不到该列完全不可能。只有一列的情况下回到该列的方案数为2，即A1->A2， 或者A2->A1
最后罗列出从第一列到最后一列的总共刷墙方案数。
ans += 2*((dp[i-1][0]+dp[i-1][1])*dp[n-i][0])) + 2*((dp[n-i)[0]+dp[n-i][1])*dp[i-1][0])
即从第i列开始刷，先刷右边的格子，有dp[n-i][0]种方案，因为要刷回来才可以刷左边的格子，然后再刷左边的格子，总共有(dp[i-1][0]+dp[i-1][1])种方案。同理可以先刷左边的格子再刷右边的格子
Tips：
nothing？因为公式的推理比较重要..
Code：
#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std; const int MAXN = ;
const int mod = ; long long dp[MAXN][];
long long ans[MAXN] = {, }; void init()
{
dp[][] = , dp[][] = ;
dp[][] = , dp[][] = ;
for (int i = ; i < MAXN; ++i) {
dp[i][] = *dp[i-][]%mod;
dp[i][] = (*(dp[i-][]%mod+dp[i-][]%mod)%mod + *(dp[i-][]%mod+dp[i-][]%mod)%mod)%mod;
} for (int i = ; i < MAXN; ++i) {
ans[i] = (dp[i][]%mod+dp[i][]%mod)%mod;
ans[i] = (ans[i]*)%mod;
for (int j = ; j < i; ++j) {
ans[i] += (*((dp[j-][]+dp[j-][])%mod*dp[i-j][]%mod)%mod)%mod;
ans[i] += (*((dp[i-j][]+dp[i-j][])%mod*dp[j-][]%mod)%mod)%mod;
}
ans[i] %= mod;
} } int main()
{
int n;
init();
while (~scanf("%d", &n)) {
printf("%lld\n", ans[n]);
}
return ;
}