[蓝桥杯 2022 省 B] 积木画

题目描述

小明最近迷上了积木画，有这么两种类型的积木，分别为 \(I\) 型（大小为 \(2\) 个单位面积) 和 \(L\) 型 (大小为 \(3\) 个单位面积):

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

输入格式

输入一个整数 \(N\)，表示画布大小。

输出格式

输出一个整数表示答案。由于答案可能很大，所以输出其对 \(1000000007\)（即 \(10^9+7\)）取模后的值。

样例 #1

样例输入 #1

3

样例输出 #1

5

提示

【样例说明】

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

【评测用例规模与约定】

对于所有测试用例，\(1 \leq N \leq 10^7\)。

蓝桥杯 2022 省赛 B 组 G 题。

状态的分析以及状态存储的优化方式

本题类似 Acwing291. 蒙德里安的梦想 故因此可以想到应该用二维的状态表示，状态f[i, j]表示为在放好前i列时，第i + 1列的状态为j，状态表示的属性时方法数，因此本题的答案就是f[n,0]。但是本题与蒙德里安不同的地方在于，本题是2 × N的棋盘，有2种积木并且N最大为10⁷，由于对于每一列来说，只有三种情况，第一种是该列的0个格子被填充，第二种是该列的1个格子被填充，第三种是该列的2个格子被填充。

因为三种状态分别对应0个、1个、2个格子被填充，所以我们可以用0、1、2分别分别去对应这三种状态。

由于本题的N比较大，如果去开一个N × 3的数组有可能导致有的测试点Memory Limit Exceeded，所以我们应该去优化我们状态的存储。因为每一个状态只和它的前一个状态有关，所以我们可以用一个滚动数组f[2, 3]去存储我们的方法数。

注：图一的状态表示应该是在放好前i列时，第i + 1列的状态为j

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1e9 + 7; // 答案可能非常大，所以题目要求取模
int n;
ll f[2][3]; // 答案可能非常大，亲测会爆int，所以开long long
int main()
{
    scanf("%d", &n);

    // 对初始状态进行初始化

    // 初始状态1：第一列竖着放一个的条形积木
    f[1][0] = 1;
    //初始状态2：第一列放一个L形状的积木，但是有正放和反放的区别
    f[1][1] = 2;
    //初始状态3：第一列横着放两个条形积木
    f[1][2] = 1;

    //状态计算
    for (int i = 2; i <= n; i ++ )
    {
        // 第一种情况:当前列竖着放一个长条与前一列以及满了
        f[i & 1][0] = (f[(i - 1) & 1][0] + f[(i - 1) & 1][2]) % MOD;
        // 第二种情况:当前列放一个L型（区分正反）与当前列被占了一格再横着放一个长条
        f[i & 1][1] = (f[(i - 1) & 1][0] * 2 + f[(i - 1) & 1][1]) % MOD;
        // 第三种情况:当前列横着放两个长条和一个L型的摆成7字形状
        f[i & 1][2] = (f[(i - 1) & 1][0] + f[(i - 1) & 1][1]) % MOD;
    }
    // 答案
    printf("%d", f[n & 1][0]);

    return 0;
}

来自wangbbb