Medium

题目描述

有一个有 n 个顶点的正凸多边形。顶点按顺时针方向从 0 到 n - 1 标记，每个顶点上恰好有一只猴子。下图展示了一个有 6 个顶点的凸多边形。

同时，每只猴子移动到相邻的顶点。如果移动后至少有两只猴子停留在同一个顶点上或在边上相交，就会发生碰撞。

返回猴子移动时至少发生一次碰撞的方法数。由于答案可能很大，返回对 10^9 + 7 取模的结果。

示例 1：

输入：n = 3
输出：6
解释：总共有 8 种可能的移动方式。
其中 2 种会发生碰撞的方式：
- 猴子 1 顺时针移动；猴子 2 逆时针移动；猴子 3 顺时针移动。猴子 1 和 2 发生碰撞。
- 猴子 1 逆时针移动；猴子 2 逆时针移动；猴子 3 顺时针移动。猴子 1 和 3 发生碰撞。

示例 2：

输入：n = 4
输出：14

约束条件：

  • 3 <= n <= 10^9

提示：

  • 尝试计算猴子不会碰撞的方法数。

解题思路

这是一道数学问题，关键是理解题目并找到规律。

思路分析：

每只猴子有两种移动选择：顺时针或逆时针移动到相邻顶点。因此总的移动方案数为 2^n。

题目要求的是"至少发生一次碰撞"的方案数，我们可以用补集思想：

  • 总方案数 - 不发生碰撞的方案数 = 至少发生一次碰撞的方案数

什么情况下不会发生碰撞？

  • 所有猴子都朝同一个方向移动（全部顺时针或全部逆时针）
  • 这样每只猴子都会移动到下一个相邻位置，不会有两只猴子到达同一位置

因此不碰撞的方案数只有 2 种：

  1. 所有猴子都顺时针移动
  2. 所有猴子都逆时针移动

所以答案为：2^n - 2

实现要点：

  • 由于 n 可达 10^9，需要使用快速幂算法计算 2^n mod (10^9 + 7)
  • 注意处理模运算，确保结果非负

代码实现

class Solution {
public:
    int monkeyMove(int n) {
        const int MOD = 1e9 + 7;
        
        // 快速幂计算 2^n mod MOD
        long long base = 2;
        long long exp = n;
        long long result = 1;
        
        while (exp > 0) {
            if (exp % 2 == 1) {
                result = (result * base) % MOD;
            }
            base = (base * base) % MOD;
            exp /= 2;
        }
        
        // 总方案数 - 不碰撞方案数
        return (result - 2 + MOD) % MOD;
    }
};

class Solution:
    def monkeyMove(self, n: int) -> int:
        MOD = 10**9 + 7
        
        # 使用Python内置的pow函数进行快速幂
        total = pow(2, n, MOD)
        
        # 总方案数 - 不碰撞方案数
        return (total - 2) % MOD

public class Solution {
    public int MonkeyMove(int n) {
        const int MOD = 1000000007;
        
        // 快速幂计算 2^n mod MOD
        long baseNum = 2;
        long exp = n;
        long result = 1;
        
        while (exp > 0) {
            if (exp % 2 == 1) {
                result = (result * baseNum) % MOD;
            }
            baseNum = (baseNum * baseNum) % MOD;
            exp /= 2;
        }
        
        // 总方案数 - 不碰撞方案数
        return (int)((result - 2 + MOD) % MOD);
    }
}

/**
 * @param {number} n
 * @return {number}
 */
var monkeyMove = function(n) {
    const MOD = 1000000007;
    
    function modPow(base, exp, mod) {
        let result = 1;
        base = base % mod;
        while (exp > 0) {
            if (exp % 2 === 1) {
                result = (result * base) % mod;
            }
            exp = Math.floor(exp / 2);
            base = (base * base) % mod;
        }
        return result;
    }
    
    const totalWays = modPow(2, n, MOD);
    const noCollisionWays = 2;
    
    return (totalWays - noCollisionWays + MOD) % MOD;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(log n)
空间复杂度O(1)

说明：

  • 时间复杂度：快速幂算法的时间复杂度为 O(log n)
  • 空间复杂度：只使用了常数个变量，空间复杂度为 O(1)

相关题目