时间：1.0s 内存：256.0MB
问题描述
X国的一段古城墙的顶端可以看成 2*N个格子组成的矩形（如下图所示），现需要把这些格子刷上保护漆。
输入格式
输入数据为一个正整数（不大于1000）
输出格式
输出数据为一个正整数。
样例输入
2
样例输出
24
样例输入
3
样例输出
96
样例输入
22
样例输出
3596357
题解：
设a[x]为4个角中任意一个格子为起始点的总方案数，b[x]为4个角中任意一个格子为起始点，其上或者其下的格子为终点的方案数。
对于b[x]，后面的每一列都必须有1个格子过去1个格子回来才能回到终点，所以b[x]=2*b[x-1];
对于a[x],以左上角的格子为例，有三个方向可以走，分类如下：
起点在角上的总方案数
起点在中间的总方案数
#include<iostream>
#define ll long long
#define inf 1000000007
using namespace std;
ll a[1011],b[1011];
int main()
{
int n;
scanf("%d",&n);
b[1]=1,a[1]=1;
b[2]=2,a[2]=6;
for(int i=3;i<=n;i++){
b[i]=b[i-1]*2%inf;
a[i]=(2*a[i-1]+4*a[i-2]+2*b[i-1])%inf;
}
ll ans1,ans2;
if(n==1){
printf("2\n");
}else{
ans1=4*a[n]%inf;
ans2=0;
for(int i=2;i<n;i++)
ans2+=8*(b[i-1]*a[n-i]%inf+b[n-i]*a[i-1]%inf)%inf;
printf("%lld\n",(ans1+ans2)%inf);
}
return 0;
}