个人博客页: https://www.scriptboy.cn/198.html
出处: 蓝桥杯 http://lx.lanqiao.cn/problem.page?gpid=T38
题目描述:
X 国的一段古城墙的顶端可以看成 2*N 个格子组成的矩形(如下图所示), 现需要把这些格子刷上保护漆.
你可以从任意一个格子刷起, 刷完一格, 可以移动到和它相邻的格子(对角相邻也算数), 但不能移动到较远的格子(因为油漆未干不能踩!)
比如: a d b c e f 就是合格的刷漆顺序.
c e f d a b 是另一种合适的方案.
当已知 N 时, 求总的方案数. 当 N 较大时, 结果会迅速增大, 请把结果对 1000000007 (十亿零七) 取模.
输入:
输入数据为一个正整数(不大于 1000)
输出:
输出数据为一个正整数.
样例输入:
2 3 22
样例输出:
24 96 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 和 2*(N-i)的矩形, 需要其中一个矩形使用第 2 种刷法刷才能回到另一个矩形中.
参考: https://blog.csdn.net/roosevelty/article/details/50706322
AC 代码:
#include #define mod 1000000007 using namespace std; long long a[1005], b[1005], sum; int main() { int N; while(cin>> N) { sum = 0; b[1] = 1; for(int i = 2; i <= N; i++) { b[i] = b[i-1] * 2 % mod; } a[1] = 1; a[2] = 6; for(int i = 3; i <= N; i++) { a[i] = b[i] + a[i-2]*4 + a[i-1]*2; a[i] %= mod; } sum += 4*a[N]; // 四个角的情况 // 中间为起点的情况 for(int i = 2; i < N; i++) { sum += (2*b[i]*2*a[N-i]+2*a[i-1]*2*b[N-i+1])%mod; } if(N == 1) sum = 2; cout << sum %mod << endl; } return 0; }
来源: https://www.cnblogs.com/lxmwb/p/9043996.html