【HDU-6146】Pokémon GO（dp）

#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;
}