试题 历届试题 格子刷油漆
问题描述
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
思路：
固定起点，由于如果起点在中间（第2~N-1列）可以分为左右两边来讨论，这时起点都是角格子。假如a[i]表示2*i的格子从左上角开始刷刷完所有格子的方案数（其中i表示列数，1<=i<=N），有三种刷法刷完所有格子：
- 先向下刷（即先刷左下角），向下刷完之后有两种方法跳到下一列，刷完剩下的i-1列需要2*a[i-1]
- 向下一列刷，最后刷左下角，可以看出不能同列刷，只能一直向右刷，且在没有到最后一列之前是不能返回，所以刷完所有格子有2^i个方案；（此种情况比较特殊，后面需要还要用到，所以单独用b[i]存储下来）
- 向下一列刷，有两种方案到下一列，然后返回左下角，再刷下一列未刷格子之后，然后有两种方案再到下一列，可见有四种方案到下下列，所以刷完所有格子有4*a[i-2]个方案；
总之，就是左下角格子什么时候刷，造成了不同的情况。如果是起点不在角格子上，不难看出，可以将左右两侧分割成 2(i-1) 和 2(N-i) 的矩形，需要其中一个矩形使用第2种刷法刷才能回到另一个矩形中。**
因为有4个角，所以从角出发总共有4 * a[n]种方案。
假如不从角出发，那么肯定不能先把这一列刷完再往两边刷，所以就是先刷一个，再先刷前边（有上下2个选择），最终回到起点下方这个格子，最后再不计终点地刷完后边的格子（开始有上下2个选择）；或者先刷后边，最终回到起点下方这个格子，最后再不计终点地刷完前边的格子。再因为开始选择的起点可以有上有下，故t = 2 * (2 * b[i - 1] * 2 * a[n - i]) + 2 * ( 2 * b[n - i] * 2 * a[i - 1])。（2 <=i < n，i即为初始选择的格子所在的列）
代码如下：
#include <stdio.h>
#define mod 1000000007
long long b[1003], a[1003], sum;int main()
{int i, n;scanf("%d", &n);b[1]=1;for(i=2; i<=n; i++) //初始化b[]数组 {b[i] = b[i-1]*2 % mod;}a[1]=1; //初始化a[]数组 a[2]=6;for(i=3; i<=n; i++){ //分别对应：先刷同列、先刷下一列再回刷、先刷2列 a[i]=(2*a[i-1] + b[i] + 4*a[i-2]) % mod;}//四个角的情况 sum = 4 * a[n] % mod; //中间的情况 for(i=2; i<n; i++){sum = (sum + 8 * b[i - 1] * a[n - i] % mod + 8 * b[n - i] * a[i - 1] % mod) % mod;}printf("%lld\n", sum);return 0;
}
