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;
})
