百度之星2017复赛1003 HDU-6146 Pokémon GO
题意
两行n列，只能到相邻格子，可以斜着。求遍历的方案数。
题解
代码
代码语言：javascript复制#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("%lldn",ans);
}
return 0;
}
