猴子碰撞的方法数

标签: 递归 数学

难度: Medium

现在有一个正凸多边形，其上共有 n 个顶点。顶点按顺时针方向从 0 到 n - 1 依次编号。每个顶点上 正好有一只猴子 。下图中是一个 6 个顶点的凸多边形。

每个猴子同时移动到相邻的顶点。顶点 i 的相邻顶点可以是：

  • 顺时针方向的顶点 (i + 1) % n ，或
  • 逆时针方向的顶点 (i - 1 + n) % n 。

如果移动后至少有两只猴子停留在同一个顶点上或者相交在一条边上，则会发生 碰撞 。

返回猴子至少发生 一次碰撞 的移动方法数。由于答案可能非常大，请返回对 109+7 取余后的结果。

注意，每只猴子只能移动一次。

示例 1：

输入：n = 3
输出：6
解释：共计 8 种移动方式。
下面列出两种会发生碰撞的方式：
- 猴子 1 顺时针移动；猴子 2 逆时针移动；猴子 3 顺时针移动。猴子 1 和猴子 2 碰撞。
- 猴子 1 逆时针移动；猴子 2 逆时针移动；猴子 3 顺时针移动。猴子 1 和猴子 3 碰撞。
可以证明，有 6 种让猴子碰撞的方法。

示例 2：

输入：n = 4
输出：14
解释：可以证明，有 14 种让猴子碰撞的方法。

提示：

  • 3 <= n <= 109

Submission

运行时间: 24 ms

内存: 15.9 MB

class Solution:
    def monkeyMove(self, n: int) -> int:
        
        # 定义模数
        MOD = 10 ** 9 + 7

        # 计算总的移动方式：2^n
        total_ways = pow(2, n, MOD)

        # 减去不会发生碰撞的移动方式：2（全部顺时针和全部逆时针）
        collisions = (total_ways - 2) % MOD

        return collisions

Explain

这道题目要求计算至少一次碰撞发生的猴子移动方式总数。猴子可以选择向顺时针或逆时针方向移动，因此对于 n 个猴子，每个猴子有两种移动选择，共有 2^n 种可能的移动方式。其中只有两种情况不会发生碰撞：所有猴子都向顺时针移动，或所有猴子都向逆时针移动。题解的思路是首先计算出所有可能的移动方式，然后从中减去这两种不会发生碰撞的情况，余下的即为至少发生一次碰撞的移动方式。

时间复杂度: O(log n)

空间复杂度: O(1)

# 定义一个解决方案类
class Solution:
    def monkeyMove(self, n: int) -> int:
        # 定义用于取模的常数
        MOD = 10 ** 9 + 7

        # 计算所有可能的移动方式，即每个猴子有两种选择，共有2^n种方式
        total_ways = pow(2, n, MOD)

        # 从所有可能的移动方式中减去两种不会发生碰撞的方式（全顺时针和全逆时针）
        collisions = (total_ways - 2) % MOD

        # 返回会发生碰撞的移动方式的数量
        return collisions

Explore

当所有猴子均选择相同的移动方向（全顺时针或全逆时针）时，每个猴子在移动过程中的相对位置保持不变，因此不会与其他猴子发生位置上的交叉或重叠，从而避免碰撞。反之，如果猴子们选择了不同的移动方向，至少有一对猴子的移动方向相反，这会导致它们在某一点相遇，从而发生碰撞。

快速幂算法是一种高效的计算幂运算的方法，尤其适用于大数的幂运算。传统的幂运算方法通过连续乘法进行，时间复杂度为O(n)。而快速幂算法利用幂的二进制表示，将幂运算分解为更小的幂的乘积，通过递归或迭代的方式，每次将幂减半，从而将时间复杂度降至O(log n)。例如，计算2^13可以分解为(2^6)^2 * 2，通过递归计算2^6，再平方，并最后乘以2来得到结果。这种方法大大减少了乘法操作的次数，提高了计算效率。

在进行模运算时，可能存在减法操作后的结果为负数的情况，尤其是当从总的移动方式中减去不会发生碰撞的两种情况时，如果不进行再次的模运算，结果可能是负数。通过再次使用MOD运算，可以确保得到的结果始终是非负的并且在合理的范围内。此外，再次模运算也有助于保持整个计算过程中数值的稳定和高效管理，避免因数值过大而导致的计算误差或超出计算机处理能力。