标题：格子刷油漆
X国的一段古城墙的顶端可以看成 2*N个格子组成的矩形（如图1所示），现需要把这些格子刷上保护漆。
你可以从任意一个格子刷起，刷完一格，可以移动到和它相邻的格子（对角相邻也算数），但不能移动到较远的格子（因为油漆未干不能踩！） 比如：a d b c e f 就是合格的刷漆顺序。 c e f d a b 是另一种合适的方案。 当已知 N 时，求总的方案数。当N较大时，结果会迅速增大，请把结果对 1000000007 (十亿零七) 取模。 输入数据为一个正整数（不大于1000） 输出数据为一个正整数。 例如： 用户输入：
2 程序应该输出：
24 再例如： 用户输入：
3 程序应该输出：
96 再例如： 用户输入：
22 程序应该输出：
359635897
#include <stdio.h> long long a[1001],b[1001],sum;//int 会超，所以long long #define NUM 1000000007 int main() { int i,n; scanf("%d",&n); //dp //总体分为 1:从边缘的出发 2:从中间出发 //1. //a[i]数组表示从最边缘的四个格子中某个出发，遍历完长度为i，个数为2i个格子的所有种类数； //b[i]数组表示从除了最边缘的四个格子外的某个中间的格子出发，遍历完一边回到所对的格子； //第一种情况一直向右走,假设从a点出发，每一列随机只走一格，也就是每向右只走一步，就是数组b[i]的存储 //第二种情况就是先走a所对的格子，然后再走下一列，当前就有两种情况，以此类推2 * a[i - 1] /*第三种考虑会往回走的情况，从第一列到第三列，会经过第二列，比如N = 3的情况， 要走到第三列，只有abcd ,abdc, adbc, acbd 四种情况。*/ //综上：a[i] = (2 * a[i-1] + b[i] + 4 * a[i-2]) b[1] = 1; for (i = 2; i <= n; i++) b[i] = (b[i-1] * 2 % NUM); a[1] = 1; a[2] = 6; for (i = 3; i <= n; i++) a[i] = (2 * a[i-1] + b[i] + 4 * a[i-2]) % NUM; sum = 4 * a[n]; //四个角，所以*4 //2.下面再 加上从中间出发的种数 /* 从第i列开始,则前面有i-1列，后面有n-i列 总的走法是：先遍历左边后右边 + 先遍历右边后左边 == 2*(2*b[i - 1]*2*a[n - i]) + 2*(2*b[n - i]*2*a[i - 1]); */ for (i = 2; i < n; i++) sum += ((8*b[n-i]*a[i-1]%NUM)%NUM + (8*a[n-i]*b[i-1])%NUM) % NUM; if(n == 1)PRintf("2/n"); else printf("%lld/n",sum); return 0; }新闻热点
疑难解答
