自动搬运

查看原文

来自洛谷，原作者为

	Infinite_Eternity 『放肆梦一场，谁说永夜中照不进天光，当乌云散去，自有漫天繁星』

搬运于2025-08-24 22:42:27，当前版本为作者最后更新于2023-01-06 11:22:32，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Description

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

用 $\text{I}$ 型积木（大小为 $2$ 个单位面积）和 $\text{L}$ 型积木（大小为 $3$ 个单位面积）填充 $2 \times n$ 的画布（积木可以任意旋转）。求出不重复方案数，结果对 $10^9+7$ 取模。

数据范围：$1 \leq n \leq 10^7$。

Analysis

首先，我们定义 $F_n$ 为填满 $2\times n$ 画布的方案总数，边界条件：

• $F_0 = 1$，表示无需再填；
• $F_k(k<0)$，表示无意义情况。

考虑最后放的情况：

1. 放 $1$ 个 $\text{I}$ 型积木（竖放）：方案数为 $F_{n-1}$；（如 $\small\text{图1}$）

2. 放 $2$ 个 $\text{I}$ 型积木（横放）：方案数为 $F_{n-2}$；（如 $\small\text{图2}$）

3. 放 $1$ 个 $\text{L}$ 型积木（因为该积木可以翻转着放，所以这样放的总方案数要 乘 $2$ ）：然而，这么填会突出 $1$ 个格子，如何消去这个突出？

   • 再放 $1$ 个 $\text{L}$ 型积木，恰好消去突出，方案数 $F_{n-3}$；（如 $\small\text{图3\,-\,1}$）
   • 横放 $1$ 个 $\text{I}$ 型积木，再放 $\text{L}$ 型积木，方案数 $F_{n-4}$；（如 $\small\text{图3\,-\,2}$）
   • $\text{I}$ 型积木可以交替着放下去，再补上一个 $\text{L}$ 型积木，从而消去这个突出。
   • 直到 $\text{I}$ 型积木和 $\text{L}$ 型积木恰好填满画布（$F_0$）。

综上，最后放 $1$ 个 $\text{L}$ 型积木得到的方案数为 $2\times (F_{n-3}+F_{n-4}+\cdots+F_{0})$。

综合 $3$ 种情况，得：

$$F_n=\left(\sum_{i=0}^{n-1}F_i\right)+\left(\sum_{i=0}^{n-3}F_i \right) $$

我们令 $n=k$，得：

$$F_k=\left(\sum_{i=0}^{k-1}F_i\right)+\left(\sum_{i=0}^{k-3}F_i \right) =F_{k-1}+F_{k-2}+2\cdot F_{k-3} +2\cdot \left(\sum_{i=0}^{k-4}F_i \right) $$

再令 $n=k-1$，得：

$$F_{k-1} = \left(\sum_{i=0}^{k-2}F_i\right)+\left(\sum_{i=0}^{k-4}F_i \right) = F_{k-2}+F_{k-3}+2\cdot \left(\sum_{i=0}^{k-4}F_i \right) $$

上式减去下式，得：

$$F_k - F_{k-1} = F_{k-1}+F_{k-3}$$

移项得：

$$F_k = 2\cdot F_{k-1}+F_{k-3}$$

于是化简得：

$$F_n=\left(\sum_{i=0}^{n-1}F_i\right)+\left(\sum_{i=0}^{n-3}F_i \right)=2\cdot F_{n-1}+F_{n-3} $$

Code

#include <stdio.h>
const int mod = 1e9+7,N = 1e7;
int main()
{
    int f[N]={0,1,2,5};
    int n;
    scanf("%d",&n);
    for(int i=4;i<=n;++i)
        f[i] = (2*f[i-1]%mod+f[i-3]%mod)%mod;
    printf("%d",f[n]);
    return 0;
}