百度之星2017复赛1003 HDU-6146 Pokémon GO

题意

两行n列，只能到相邻格子，可以斜着。求遍历的方案数。

题解

dp[i]从一个点出发遍历长度i最后回到这一列的方案数

dp2[i]从一个点出发遍历长度i的方案数

显然有\(dp[i]=2*dp[i-1]\)。

dp2[i]就要考虑3种情况：先遍历后面的格子，最后回到当前列，\(2*dp[i-1]\); 先完成当前列，再去别的格子，\(2*dp2[i-1]\); 先遍历下一列，再回来，再遍历后面的列，\(4*dp2[i-2]\)。

然后枚举从第i列出发，向前面走再回到第i列dp[i]，再遍历后面的格子dp2[n-i]，也可以先向后。

代码

#include <bits/stdc++.h>

#define mem(a,b) memset(a,b,sizeof(a))

#define ll long long

#define N 10005

const ll M = 1e9+7;

using namespace std;

int t,n;

ll dp[N];//start from x and back to x,length i

ll dp2[N];//start from x, length i

int main(){

    dp[1]=1;

    for(int i=2;i<N;++i)dp[i]=(dp[i-1]<<1)%M;

    dp2[1]=1;dp2[2]=6;

    for(int i=3;i<N;++i)dp2[i]=(dp2[i-2]*4+dp2[i-1]*2+dp[i-1]*2)%M;

    scanf("%d",&t);

    while(t--){

        scanf("%d",&n);

        ll ans=0;

        if(n==1)ans=2;

        else ans=dp2[n]*4;

        for(int i=2;i<=n-1;++i)

           ans=(ans+(dp[i]*dp2[n-i]%M+dp[n-i+1]*dp2[i-1]%M)*4%M)%M;

        printf("%lld\n",ans);

    }

    return 0;

}