问题描述
X国的一段古城墙的顶端可以看成 2*N个格子组成的矩形（如下图所示），现需要把这些格子刷上保护漆。
你可以从任意一个格子刷起，刷完一格，可以移动到和它相邻的格子（对角相邻也算数），但不能移动到较远的格子（因为油漆未干不能踩！）
比如：a d b c e f 就是合格的刷漆顺序。
c e f d a b 是另一种合适的方案。
当已知 N 时，求总的方案数。当N较大时，结果会迅速增大，请把结果对 1000000007 (十亿零七) 取模。
输入格式
输入数据为一个正整数（不大于1000）
输出格式
输出数据为一个正整数。
样例输入
2
样例输出
24
样例输入
3
样例输出
96
样例输入
22
样例输出
359635897
解题思路：参考
https://blog.csdn.net/u010126535/article/details/20651999
https://blog.csdn.net/a1995115/article/details/27529747
相对的格子表示一列之中，除了指定格子之外的另一个格子。
- 构造数组a[x]、b[x]。a[x]表示在2 * x的格子条件下，从四个角任意一个角的格子出发，遍历全体格子的方法总数，b[x]表示在2 * x的条件下，从四个角任意一个角的格子出发，遍历全体格子后回到与之相对的格子中的方法总数。
显然，a[1]=1，b[1]=1。
递推式：
a[x]=
b[x]=b[x-1] * 2
推导如下：
- 先考虑出发点在角上，从一个角出发，只有3种可能性。
（1）先去同一列相邻的格子，然后前往下一列，这就简化成从2 * (x-1)的格子中，从一个角出发，遍历全体格子的 问题。因为前往下一列有两种选法，所以有2 * a[x-1]种方法。
（2）先去相邻列的同一行的格子。又分为：
先去左下角，再去右边部分， a[x-2] * 2种方法
先遍历右边的所有，再回来左下角，b[x-1]种方法
（3）先去右下角的格子，又分为：
先去左边格子，再遍历右边，a[x-2] * 2种方法
先遍历右边，再去左边，b[x-1]种方法
如图~
整理可得
a[x]=a[x-1] * 2+a[x-2] * 4+b[x-1] * 2
b[x]=2 * b[x-1]
而从中间某列的一点（2种选择）出发时，显然不能直接往下走，否则无法遍历所有的点，应当先遍历左边（右边）左右的点，然后回到相对的点，再遍历右边（左边）的点。假设从第i列出发，出发的点有两种选择，第二步也有两种选择，因此所有的走法有2 * (b[i-1] * 2 * 2 * a[n-i]+ 2 * b[n-i] * 2 * a[i-1])种。加法的前一半时先遍历左边，后一半是先遍历右边。
于是，总数就是4 * a[x]+Σ（2到n-1）2 * (b[i-1] * 2 * 2 * a[n-i]+ 2 * b[n-i] * 2 * a[i-1])
献上代码啦
#include<iostream>
using namespace std;
int main() {
int n;
cin >> n;
long long int sum = 0;
long long int def = 1000000007;
long long int a[1001], b[1001];
a[0] = 0;
b[0] = 0;
a[1] = 1;
b[1] = 1;
a[2] = 6;
b[2] = 2;
for (int i = 3; i <= n; i++) {
b[i] = 2 * b[i - 1];
b[i] %= def;
a[i] = 2 * a[i - 1] + a[i - 2] * 4 + b[i];
a[i] %= def;
}
sum = a[n] * 4;
for (int i = 2; i <= n - 1; i++) {
sum += 2 * (b[i - 1] * 2 * 2 * a[n - i]%def + 2 * b[n - i] * 2 * a[i - 1]%def)%def;
sum %= def;
}
if (n == 1)
sum = 2;
if (n == 2)
sum = 24;
cout << sum;
system("pause");
return 0;
}
写代码时尤其要注意，因为数据较大，所以都要用long long int型，否则从long long 到int可能会丢失数据，还要注意结果取模。
网友评论