个人博客页:https://www.scriptboy.cn/198.html
出处:蓝桥杯
题目描述:
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]
;b[i]
存储下来)4*a[i-2]
个方案; 总之,就是左下角格子什么时候刷,造成了不同的情况。如果是起点不在角格子上,不难看出,可以将左右两侧分割成2*i
和2*(N-i)
的矩形,需要其中一个矩形使用第2种刷法刷才能回到另一个矩形中。
参考:https://blog.csdn.net/roosevelty/article/details/50706322
AC代码:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | #include <bits/stdc++.h> #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; } |
---|