P8607 题解

· · 题解

题目传送门

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

思路

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

很多同学的第一想法是搜索，但在本题 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]
  1. 现假设初始情况下从顶点A出发。根据描述，第一步可以选C或D作为接下来的落点（假设我们选的是C）；那么接下来又可以选择E或F作为第二步的落点（假设我们选的是E）……当走到最后一列（假设最后一列的落点为I），此时返回的路线也被唯一确定了。如果我们将这种“一趟过去，一趟回来”的行走方式用数组 b 来表示，则从上面的分析可知，它存在一个递推关系，即：
b[i] = 2 \times b[i - 1]
  1. 现假设初始情况下从顶点 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] 的初值。

代码

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