X国的一段古城墙的顶端可以看成 2*N个格子组成的矩形(如下图所示),现需要把这些格子刷上保护漆。
你可以从任意一个格子刷起,刷完一格,可以移动到和它相邻的格子(对角相邻也算数),但不能移动到较远的格子(因为油漆未干不能踩!)
比如:a d b c e f 就是合格的刷漆顺序。
c e f d a b 是另一种合适的方案。
当已知 N 时,求总的方案数。当N较大时,结果会迅速增大,请把结果对 1000000007 (十亿零七) 取模。
1 #include<iostream> 2 using namespace std; 3 #define MAX 1020 4 long long dp[MAX][2],ans; 5 int main(){ 6 int m; 7 cin>>m; 8 dp[1][0]=2;dp[1][1]=0; 9 dp[2][0]=4;dp[2][1]=8;10 for(int i=3;i<MAX;i++){11 dp[i][0]=(dp[i-1][0]*2)%1000000007;12 dp[i][1]=2*(dp[i-1][0]+dp[i-1][1])%1000000007+4*(dp[i-2][0]+dp[i-2][1])%1000000007;13 }14 //从两端开始回到两端 以及从两端开始不回到两端 15 ans=2*(dp[m][0]+dp[m][1])%1000000007;16 //此处累加遍历第一个被刷的格子的列 17 for(int i=2;i<m;i++){18 //从中间第i位置开始先右后左 19 ans+=(dp[i][0]*(dp[m-i][0]+dp[m-i][1]))%1000000007;20 //从中间第i位置开始先左后右 21 ans+=(dp[m-i+1][0]*(dp[i-1][1]+dp[i-1][0]))%1000000007;22 ans%=1000000007;23 }24 cout<<ans<<endl;25 return 0;26 }
测评结果:
联系客服