E. Tetrahedron - 题解

比赛与标签

比赛: Codeforces Round 113 (Div. 2) 标签: dp, math, matrices 难度: *1500

小蚂蚁的四面体漫步喵~

主人你好呀~！今天我们来帮助一只可爱的小蚂蚁解决它的散步问题，喵~

想象一下，有一个正四面体，它的四个顶点分别是 A, B, C, D。一只勤劳的小蚂蚁一开始在顶点 D。它非常活泼，每过一个单位时间，就会从当前所在的顶点沿着一条棱走到另一个相邻的顶点去，绝不会停在原地哦！

我们的任务是，计算出这只小蚂蚁从顶点 D 出发，经过 恰好 n 步 后，正好回到顶点 D 的路径总共有多少种呢？因为答案可能会非常非常大，所以我们需要将结果对 1000000007 取模。

输入: 就是一个整数 n (1 ≤ n ≤ 10^7)，代表小蚂蚁要走的总步数。

输出: 一个整数，表示回到顶点 D 的总方案数，记得要取模哦！

动态规划的奇妙旅程呐~

这道题看起来有点复杂，但只要我们抓住其中的规律，就会变得非常简单喵！最适合用动态规划 (DP) 来解决啦。

首先，我们来分析一下小蚂蚁的移动。在一个正四面体中，任何一个顶点都与其他三个顶点相连。比如说，小蚂蚁在 D 点，那么下一步它必定会移动到 A, B, C 中的某一个点。如果小蚂蚁在 A 点，那么下一步它可以移动到 B, C, D 中的某一个点。

注意到这个问题的对称性了吗？对于小蚂蚁来说，A, B, C 这三个点是完全等价的。无论它在 A, B, 还是 C，下一步可以走的选择都是一样的（另外两个非 D 顶点，以及 D 顶点）。这给了我们一个绝妙的简化思路！

我们可以把状态分为两种：

在顶点 D
不在顶点 D (也就是在 A, B, C 中的任意一个)

接下来，我们定义 DP 状态：

dp_D[i]：表示小蚂蚁走 i 步后，正好位于顶点 D 的方案数。
dp_other[i]：表示小蚂蚁走 i 步后，位于 非 D 顶点 (即 A, B, C 三个点中任意一个) 的总方案数。

初始状态 (第 0 步): 小蚂蚁还没开始走，它就在起点 D。

dp_D[0] = 1 (只有一种情况，就是在 D)
dp_other[0] = 0 (不可能在其他点)

状态转移 (从第 i-1 步到第 i 步): 我们来想想，第 i 步时小蚂蚁的位置，取决于它第 i-1 步在哪里。

如何到达 D (dp_D[i])? 要想在第 i 步到达 D，小蚂蚁在第 i-1 步必须在 A, B, C 中的某一个点。
- 如果在 A，有 1 条路到 D。
- 如果在 B，有 1 条路到 D。
- 如果在 C，有 1 条路到 D。所以，第 i 步到达 D 的总方案数，就等于第 i-1 步到达 A, B, C 的总方案数之和。也就是 dp_other[i-1]。
dp_D[i] = dp_other[i-1]
如何到达非 D 顶点 (dp_other[i])? 要想在第 i 步到达非 D 顶点，小蚂蚁在第 i-1 步可能在 D，也可能在另一个非 D 顶点。
- 情况一：从 D 出发。 如果第 i-1 步在 D (有 dp_D[i-1] 种方案)，那么下一步它可以去 A, B, C，共有 3 种选择。这部分贡献的方案数是 3 * dp_D[i-1]。
- 情况二：从非 D 顶点出发。 如果第 i-1 步在某个非 D 顶点（比如 A），那么下一步它可以去 B, C, D。其中 B 和 C 是非 D 顶点，有 2 种选择。由于 A, B, C 是对称的，所以从任何一个非 D 顶点出发，都有 2 种方式走到另一个非 D 顶点。因此，这部分贡献的方案数是 2 * dp_other[i-1]。
dp_other[i] = 3 * dp_D[i-1] + 2 * dp_other[i-1]

我们要求的最终答案就是 dp_D[n]。

空间优化喵~ 我们发现，计算第 i 步的状态只依赖于第 i-1 步。所以我们不需要一个大数组，只需要两个变量来记录上一步的状态，然后不断迭代更新就好啦！这种方法叫做“滚动数组”或者状态压缩。

dp0：表示当前步数下，在 D 点的方案数。
dp1：表示当前步数下，在非 D 点的总方案数。

迭代 n 次，每次更新 dp0 和 dp1，就能得到最终结果了！

代码实现喵~

cpp

#include <iostream>
using namespace std;

// 定义模数，是个好习惯喵~
const int mod = 1000000007;

int main() {
    int n;
    cin >> n;

    // dp0: 表示走了 i 步后，在顶点 D 的方案数
    // dp1: 表示走了 i 步后，在其他三个顶点（A, B, C）的总方案数
    
    // 初始状态：第 0 步
    long long dp0 = 1; // 蚂蚁在 D 点，所以方案数为 1
    long long dp1 = 0; // 蚂蚁不在其他点，所以方案数为 0

    // 从第 1 步开始迭代到第 n 步
    for (int i = 1; i <= n; i++) {
        // 在更新 dp0 和 dp1 之前，先把上一步的 dp0 (即 dp_D[i-1]) 存起来
        // 因为计算新的 dp1 时需要用到它
        long long temp = dp0;

        // 更新 dp0 (计算 dp_D[i])
        // 要想到达 D，上一步必须在其他顶点。
        // 所以新的 dp0 等于旧的 dp1。
        // dp_D[i] = dp_other[i-1]
        dp0 = dp1;

        // 更新 dp1 (计算 dp_other[i])
        // 要想到达其他顶点，上一步可能在 D，也可能在其他顶点。
        // 从 D 出发有 3 种走法到其他顶点 (对应 3 * temp)。
        // 从其他顶点出发有 2 种走法到其他顶点 (对应 2 * dp1)。
        // dp_other[i] = (3 * dp_D[i-1] + 2 * dp_other[i-1]) % mod
        dp1 = (3 * temp + 2 * dp1) % mod;
    }

    // 循环结束后，dp0 就是走了 n 步后回到 D 点的方案数
    cout << dp0 << endl;

    return 0;
}

复杂度分析的说

时间复杂度: O(n) 的说。我们用一个简单的 for 循环从 1 迭代到 n，循环体内部是常数时间的操作。对于 n 最大为 10^7，这个复杂度是完全可以接受的！
空间复杂度: O(1) 的说。我们只用了 dp0, dp1, temp 等几个变量，没有使用和 n 相关的额外空间，非常节省内存呐！

知识点与总结

这道题真是太有趣啦，让我们来总结一下学到了什么吧！

动态规划 (DP): 这是解决本题的核心思想。通过定义清晰的状态和找到正确的状态转移方程，我们就能把一个大问题分解成一步步的小问题来解决。
对称性与状态压缩: 识别出 A, B, C 三个顶点的对称性是解题的关键！这让我们能把 4 个状态（A, B, C, D）压缩成 2 个状态（D, 非 D），大大简化了问题。
滚动数组思想: 当 DP 的当前状态只依赖于前一个或前几个状态时，我们就可以用少量变量来代替整个 DP 数组，将空间复杂度从 O(n) 优化到 O(1)。
模运算: 在处理可能导致整数溢出的计数问题时，一定要记得在每一步加法和乘法后都进行取模操作，以保证结果的正确性。
其他解法 (矩阵快速幂): 对于这道题，n 的范围是 10^7，O(n) 的 DP 已经足够快了。但如果 n 的范围更大（比如 10^18），O(n) 就会超时。这时，我们可以将状态转移方程写成矩阵形式，然后使用 矩阵快速幂 来求解，时间复杂度可以优化到 O(log n)！这也是 matrices 标签的由来哦。

希望这篇题解能帮助到你，主人！继续加油，享受算法的乐趣吧，喵~

E. Tetrahedron - 题解 ​

比赛与标签 ​

小蚂蚁的四面体漫步喵~ ​

动态规划的奇妙旅程呐~ ​

代码实现喵~ ​

复杂度分析的说 ​

知识点与总结 ​