2550-猴子碰撞的方法数

现在有一个正凸多边形，其上共有 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

正难则反，只有全部顺时针和全部逆时针才不会碰撞。

在不考虑碰撞时，由于每个猴子都可以往两边走，那么总共有 2^n 种移动方法。

答案所有移动方法减去不会碰撞的移动方法，即 2^n-2。用快速幂计算。

不了解快速幂的同学可以看看 50. Pow(x, n) 。

注意为了避免负数，需要在 -2 后再转换到非负数上。

附：视频讲解

[sol1-Python3]

class Solution:
    def monkeyMove(self, n: int) -> int:
        MOD = 10 ** 9 + 7
        return (pow(2, n, MOD) - 2) % MOD

[sol1-Go]

const mod int = 1e9 + 7

func monkeyMove(n int) int {
	return (pow(2, n) - 2 + mod) % mod
}

func pow(x, n int) int {
	res := 1
	for ; n > 0; n /= 2 {
		if n%2 > 0 {
			res = res * x % mod
		}
		x = x * x % mod
	}
	return res
}

复杂度分析

• 时间复杂度：O(\log n)。
• 空间复杂度：O(1)，仅用到若干变量。