P8784 [蓝桥杯 2022 省 B] 积木画 - 洛谷

题目描述

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

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

输入格式

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

输出格式

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

输入输出样例

输入 #1复制

3

输出 #1复制

5

说明/提示

【样例说明】

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

【评测用例规模与约定】

对于所有测试用例，1≤N≤1e7。

蓝桥杯 2022 省赛 B 组 G 题。

思路：

代码：
 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 10000000 + 10, mod = 1e9 + 7;
ll dp[N][3]; 
// dp[i][0] 表示第i列只有第一行凸 
// dp[i][1] 表示第i列只有第二行凸 
// dp[i][2] 表示第i列两行都凸 
int main()
{
    dp[0][2] = 1;
    dp[1][2] = 1; // 第一列只有一种放法，竖着放
    ll n;
    cin >> n;
    for(ll i = 2; i <= n; ++i)
    {
        dp[i][0] = (dp[i - 1][1] + dp[i - 2][2]) % mod;
        dp[i][1] = (dp[i - 1][0] + dp[i - 2][2]) % mod;
        dp[i][2] = (dp[i - 1][2] + dp[i - 1][0] + dp[i - 1][1] + dp[i - 2][2]) % mod;
    }
    cout << dp[n][2];
    return 0;
}