格子刷油漆

画图+手推公式.还是一道不错的题~.
首先考虑从顶点开始全部遍历的三种走法.

对于第一种和第三种,他们都走过去了,并不一定走回来.我们令其为a[],对于第二种而言,他们走过去了,又走回来了,我们令其为b[].
对于第一种情况而言呢,每次都有选这个点还是选另外一个点,所以

a[i]+=2*a[i-1].

对于第三种情况而言呢,每两格都有四种不同的走法,所以

a[i]+=a[i-2]*4.

对于第二种情况而言呢,和第一种情况是一致的,也是

b[i]=b[i-1]*2.

然后注意ai还要加上bi//
然后我们随意的枚举起点,然后这题就解决了.代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int N=1e3+5;
ll a[N],b[N];
void init()
{
    a[1]=1;b[1]=1;
    a[2]=6;b[2]=2;
    for(int i=3;i<=N-5;i++)
    {
        b[i]=(b[i]+2ll*b[i-1])%mod;
        if(i>1) a[i]=(a[i]+a[i-2]*4ll)%mod;
        a[i]=(a[i]+2ll*a[i-1]+b[i])%mod;
    }
}

int main()
{
    int n;init();
    while(cin>>n)
    {
        if(n==1)    {puts("2");continue;}
        ll ans=0;
        for(int i=2;i<n;i++)//枚举起点在哪个位子.
        {
            ans=(ans+4ll*b[i]*a[n-i]%mod+4ll*a[i-1]*b[n-i+1]%mod)%mod;
        }ans=(ans+4ll*a[n])%mod;
        cout<<ans<<'\n';
    }
    return 0;
}

细节边界挺多的.