题解 P1990 【覆盖墙壁】

Lylighte · 2020-03-27 15:49:09 · 题解

用如下两种砖块（可旋转）填充 2\times n 的墙壁，求出不重复方案数，结果对 10^4 取模。

按照惯例，定义 F_n 为填满 2\times n 墙壁的方案总数，边界条件 F_0 = 1，对于 k<0，F_k=0。（F_0 表示无需再填，F_k(k<0) 表示无意义情况）

考虑最后放的情况：

1. 放 1 个 2\times 1 的砖块（竖放）：显然它的方案数为 F_{n-1}；（图 1）

2. 放 2 个 2\times 1 的砖块（横放）：方案数为 F_{n-2}；（图 2）

3. 放 1 个 L 型砖块（因为该砖块可以翻转着放，所以这样放的总方案数要 乘 2）：这么填会带来 1 个格子的突出，如何消去这个突出？

   • 再放 1 个 L 型砖块，恰好消去突出，方案数 F_{n-3}；（图 3-1）
   • 横放 1 个 2\times 1 的砖块，再放 L 型砖块，方案数 F_{n-4}（图 3-2）；
   • 直到 2\times 1 砖块和 L 型砖块恰好填满墙壁（F_0）。

   综上，最后放 1 个 L 型砖块得到的方案数为 2\times (F_{n-3}+F_{n-4}+\cdots+F_{0})（已经乘了 2）。

综合 3 种情况，得：

如果每次都重新算前 n-1 个方案总和，很明显会超时。当然很容易能想到前缀和：

定义 \texttt{preF}_n=\sum_{i=0}^{n}F_i，即前 n 个方案数之和。对于 k<0，\texttt{preF}_k=0。很明显得出 \texttt{preF}_n=\texttt{preF}_{n-1}+F_n。

那么之前的式子可以变成：

接着就愉快地写代码：

#include <bits/stdc++.h>
int F[1000010];             //方案数
int preF[1000010];          //前缀和
int n;
int main(){
    std::cin >> n;
    F[0] = 1;
    preF[0]=1;
    for(int i=1; i<=n; i++){
        F[i]=(i-1<0?0:preF[i-1])+(i-3<0?0:preF[i-3]);   //递推，特判 k<0 的情况
        F[i] %= 10000;                                  //保留后 4 位
        preF[i] = preF[i-1]+F[i];                       //更新前缀和
        preF[i] %= 10000;
    }
    std::cout << F[n] << std::endl;     //直接输出就行了
    return 0;
}

附图（从上到下为图 1，图 2，图 3-1，图 3-2）：

2020/08/30 更新一下

来自楼上玄学题解很久以前的评论：

人话翻译一下：

注意到计算 F_k 和 F_{k-1} 时都加上了许多相同的部分（具体见下）。

令 n=k，得

令 n=k-1，得

（相同的部分是什么应该能看清吧……）

上式减去下式，得到 F_k - F_{k-1} = F_{k-1}+F_{k-3}，

移项就得到 F_k = 2\cdot F_{k-1}+F_{k-3}。

于是这个递推式就得到化简了。

于是这篇题解更新完了。

希望 LaTeX 别炸呀。