自动搬运

查看原文

来自洛谷，原作者为

	fish_gugu 这个家伙很懒`，什么也没有留下

搬运于2025-08-24 22:40:38，当前版本为作者最后更新于2024-01-09 21:39:28，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

题目传送门

警告：本题解较长，建议前往博客食用

思路

本题的实质是在已知几个基本行走规则的前提下，求解遍历整个矩形的行走路线数量。

很多同学的第一想法是搜索，但在本题 $n$ 最大可取到 $1000$ 的前提下，搜索必然超时（递归层次太深），因此我们不得不另辟蹊径。从题目的描述来看，这道题也更像是一道动态规划的题目。

对于题目给出的几类行走规则，我们可以很容易地联想到递推。因为对于某个格子，其走到当前可能有很多种走法，但是从另一个角度看来，以某个格子为出发点进行“刷漆”，其行走方式却是固定的。我们首先要做的，就是来分析这个过程，并找到动态转移方程。对城墙刷漆时，我们的起点主要分为以下两大类：

1. 从四个顶点之一出发。
2. 从中间某个点出发。

下面给出了两类的分析：

---

1. 从四个顶点出发

统一附图：

在此前提下，又可分为3小类行走方式：

• 第一步走同一列的另一个格子，第二步走下一列的任意格子……如此循环直到走完所有列。
• 第一步走下一列的任意格子，第二步再走下一列的任意格子……如此行走直到最后一列。返回时路径唯一。
• 第一步走下一列的任意格子，第二步由该格子返回前一列剩下的尚未走的格子，第三步再来到前一步所在列剩下的尚未走的格子……如此循环直到走完所有列。

下面对这些小类进行进一步分析：

1. 现假设初始情况下从顶点 A 出发。根据描述，第一步应该走向 B。接下来在 B 点时就有两种选择方案：要么走向 C；要么走向 D。而无论选择走哪一点，接下来的情形都将回到初始情况：“从某个顶点出发，走完一个 $m \times 2$ 的格子（这里的 $m$ 自然取 $n - 1$）”。如果我们将这种“一趟过去，不再返回”的行走方式用数组 $a$ 来表示，则从上面的分析可知，它存在一个递推关系，即：

$$a[i] = 2 \times a[i - 1]$$

2. 现假设初始情况下从顶点A出发。根据描述，第一步可以选C或D作为接下来的落点（假设我们选的是C）；那么接下来又可以选择E或F作为第二步的落点（假设我们选的是E）……当走到最后一列（假设最后一列的落点为I），此时返回的路线也被唯一确定了。如果我们将这种“一趟过去，一趟回来”的行走方式用数组 $b$ 来表示，则从上面的分析可知，它存在一个递推关系，即：

$$b[i] = 2 \times b[i - 1]$$

3. 现假设初始情况下从顶点 A 出发。根据描述，第一步有两条路线： A→C→B→D 或 A→D→B→C，假设最终落点为 D，则在 D 时将面临两种选择，要么到 E 要么到 F），而无论选择哪一点，接下来都将回到初始情况：“从某个顶点出发，走完一个 $m \times 2$ 的格子（这里的 $m$ 自然取 $n - 2$）。该走法也属于“一趟过去，不再返回”的类型，因此这里依然用数组 $a$ 来表示。但是注意到一点：这种行走方式从一种状态到下一种状态需要的最小行走次数为 $2$，因此其状态转移方程为：

$$a[i] = 2 \times 2 \times a[i - 2] = 4 \times a[i - 2] $$

以上便是从顶点出发刷完所有墙面的全部行走方式。但需要注意的是，在实际刷墙时，这些行走方式可以任意组合，而不仅仅是单一化的。比如，可以先用方法一走一段，再用方法二走另一段；或者先用方法三走一段，再用方法一走一段，再用方法二走最后一段……这些组合方式是不胜枚举的。因此在进行状态转移的时候，我们需要将上面这三种情况都加到一起。在这样的前提下，我们可以直接将 $a$ 数组的含义赋予为“从墙壁顶点处出发，刷完整面墙的方案数”，于是可以得到新的状态转移方程为：

$$a[i] = 2 \times a[i - 1] + b[i] + 4 \times a[i - 2] $$

对于“一趟过去，一趟返回”的走法而言，他是独特的，因为他的遍历路径不能插入其他任何遍历方式：其只有两趟，一趟必须到底，另一趟则走剩余路径。因此他的走法在迭代时，与其他走法（方法一、方法三）没有任何关系，而仅仅取决于其前一种状态。所以它的状态转移方程为：

$$b[i] = 2 \times b[i - 1]$$

注：由于从顶点出发时有 $4$ 个顶点，因此最后的结果实际上是 $4 \times a[n]$。

---

2.从中间出发

统一附图：

由于墙的高度为 $2$ 且不能走已经刷过的点，因此从中间某个点出发时必然是先刷该点的某一边，然后再倒回来刷该点的另一边。见下图，假设我们从图中 $i = 3$（E 点）处出发（以 $i = 3$ 为分割线，将图分为左边的 ABCDEF 以及右边的 GHIJ），为了遍历所有格子，我们必须先走完左边的 ABCDEF 才能继续走右边的 GHIJ（注意：出发点为 E 时，回来的终点必须是 F），然后再把右边的 GHIJ 视为以 G（或 H）为起点的一组格子，并将其走完（因此这里有两个出发点，所以需要乘以 $2$）。

在上面的遍历过程中，当从 E 点出发并往左边走时，由于其必须返回到 $i = 3$ 列的 F 点，因此属于“一趟过去，一趟回来”的类型。在左边长度为 $i = 3$ 时，左边的遍历方式就有 $b[i]$ 种；当从 F 出发时，由于其有两个落点（G 或 H），因此这里要乘以 $2$。接下来，无论在哪一个点出发，此时既可以选择“一趟过去，一趟回来”，也可以选择“一趟过去，不再返回”，还可以选择两者的任意合法组合。总之，就是前面我们已经修改后的 $a$ 数组（从墙壁顶点处出发，刷完整面墙的方案数）。于是，可以得到整个右边的行走方式有 $2 \times a[n - i]$ 种。于是，可以得到从E点出发先往左侧移动时，总的刷漆方式有 $b[i] \times 2 \times a[n - i]$ 种。此外，一开始时，我们还可以选择从 F 点出发，然后回到 E 点，所以这里还需要再乘以 $2$，即：

$$2 \times b[i] \times 2 \times a[n - i] = 4 \times b[i] \times a[n - i] $$

还有一种情况，当我们从E出发时先往右边 EFGHIJ 走（最终返回至F点），这时，该部分的遍历方案就有 $b[n - i + 1]$ 种；接下来对于左边的 ABCD，同样是“从墙壁顶点处出发，刷完整面墙的方案数”这一方式，即 $2 \times a[i - 1]$ 种（这里乘以 $2$ 依然是因为在 ABCD 部分，其出发点可以选择 C 或者 D）。于是，可得到总的刷漆方式为 $b[n - i + 1] \times 2 \times a[i - 1]$ 种。同样地，这里一开始的出发点可以选E也可以选F，所以上述方案最终还要乘以 $2$，即：

$$2 \times b[n - i + 1] \times 2 \times a[i - 1] = 4 \times b[n - i + 1] \times a[i - 1] $$

综上所述，可得到从中间出发的总方案数为：

$$4 \times (b[i] \times a[n - i] + b[n - i + 1] \times a[i - 1]) $$

---

汇总

综合方案一、方案二可以得到的最终方案数为：

$$sum = 4 \times a[n] + 4 \times (b[i] \times a[n - i] + b[n - i + 1] \times a[i - 1]) $$

下面我们来确定初值。在上面的所有相关公式中，存在的有 $a[i - 1]$，$a[i - 2]$，$b[i - 1]$ 那么我们就需要确定出 $a[1]$、$a[2]$、$b[1]$ 的初值。

• 当 $n = 1$ 时，从某个顶点出发显然只有一种行走方式，因此 $a[1] = 1$；

• 当 $n = 2$ 时，从某个顶点出发会有以下 6 种方式，见下图，因此 $a[2] = 6$。

• 当 $n = 1$ 时，对于“一趟过去，一趟返回”这种走法而言，其从某个顶点出发显然只有一种走法，即走向该列的另一个点；

• 当 $n = 2$ 时，对于“一趟过去，一趟返回”这种走法而言，其从某个顶点出发显然只有 $2$ 种方式，因此 $b[2] = 2$（为了在写代码的时候能够将 $a$ 数组和 $b$ 数组放进同意循环，这里也顺带给出了 $b[2]$ 的值）。

---

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e9 + 7;
long long a[1005],b[1005];

int main()
{
    int n;
    cin >> n;
    if(n == 1)
    {
        cout << 2;
        return 0;
    }
    a[1] = 1,a[2] = 6;
    b[1] = 1,b[2] = 2;
    for(int i = 3;i <= n;i++)
    {
        b[i] = (2 * b[i - 1]) % N;
        a[i] = (2 * a[i - 1] + b[i] + 4 * a[i - 2]) % N;
    }
    long long sum = (4 * a[n]) % N; //必须开long long，否则有可能会溢出
    for(int i = 2;i < n;i++) sum = (sum + 4 * (b[i] * a[n - i] + b[n - i + 1] * a[i - 1])) % N;
    //根据前面算出的a数组和b数组，递推出从中间出发时的方案数量
    //注意i的范围大于1小于n
    cout << sum;
    return 0;
}