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

Infinite_Eternity · 2023-01-06 11:22:32 · 题解

Description

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

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

Analysis

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

考虑最后放的情况：

放 1 个 \text{I} 型积木（竖放）：方案数为 F_{n-1}；（如 \small\text{图1}）
放 2 个 \text{I} 型积木（横放）：方案数为 F_{n-2}；（如 \small\text{图2}）
放 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} 型积木恰好填满画布（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;
}