试题 G: 积木画

【问题描述】 小明最近迷上了积木画,有这么两种类型的积木,分别为 I 型(大小为 2 个单位面积)和 L 型(大小为 3 个单位面积):

同时,小明有一块面积大小为 2 × N 的画布,画布由 2 × N 个 1 × 1 区域构成。小明需要用以上两种积木将画布拼满,他想知道总共有多少种不同的方式? 积木可以任意旋转,且画布的方向固定。

【输入格式】 输入一个整数 N,表示画布大小。

【输出格式】 输出一个整数表示答案。由于答案可能很大,所以输出其对 1000000007 取 模后的值

【样例输入】 3

【样例输出】 5

【样例说明】 五种情况如下图所示,颜色只是为了标识不同的积木:

【评测用例规模与约定】 对于所有测试用例,1 ≤ N ≤ 10000000.


用 f[i] 表示i列的方法总数

接下来把状态分一下类

1. 第 i-1列已经排满的基础上,如图,方法数等于f[i-1]

2.若第 i-1列没排任何积木(即与第i列构成如下图),方法数等于f[i-2]

3.

①若第 i-1列排了一半,只有如下两种情况, 方法数等于2*f[i-3]

②上面的情况并不全面, 我发现第i-3置身事外

那用不用考虑下面这种情况呢, 明显是不用的,与上面情况2重复,

新的情况已经出现!, 方法数等于2*f[i-3]

③这次把第i-4列拉下水, 这也是我们未曾考虑到的情况, 2*f[i-4]

综上, 大胆假设出:

(o゜▽゜)o☆[BINGO!]

可以看出 f[1] = 1, f[2] = 2, f[3] = 5 ,剩下的递推即可

我的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<iostream>
using namespace std;

const int N = 1e7+10, MOD = 1000000007;
int f[N];
int main()
{
f[1] = 1;
f[2] = 2;
f[3] = 5;
int n;
cin >> n;
for(int i = 4; i <= n; i ++)
{
f[i] = (2*f[i-1]%MOD + f[i-3]%MOD)%MOD;
}
cout << f[n];
return 0;
}