猴子碰撞的方法数
难度:
标签:
题目描述
There is a regular convex polygon with n vertices. The vertices are labeled from 0 to n - 1 in a clockwise direction, and each vertex has exactly one monkey. The following figure shows a convex polygon of 6 vertices.
Each monkey moves simultaneously to a neighboring vertex. A neighboring vertex for a vertex i can be:
- the vertex
(i + 1) % nin the clockwise direction, or - the vertex
(i - 1 + n) % nin the counter-clockwise direction.
A collision happens if at least two monkeys reside on the same vertex after the movement or intersect on an edge.
Return the number of ways the monkeys can move so that at least one collision happens. Since the answer may be very large, return it modulo 109 + 7.
Note that each monkey can only move once.
Example 1:
Input: n = 3 Output: 6 Explanation: There are 8 total possible movements. Two ways such that they collide at some point are: - Monkey 1 moves in a clockwise direction; monkey 2 moves in an anticlockwise direction; monkey 3 moves in a clockwise direction. Monkeys 1 and 2 collide. - Monkey 1 moves in an anticlockwise direction; monkey 2 moves in an anticlockwise direction; monkey 3 moves in a clockwise direction. Monkeys 1 and 3 collide. It can be shown 6 total movements result in a collision.
Example 2:
Input: n = 4 Output: 14 Explanation: It can be shown that there are 14 ways for the monkeys to collide.
Constraints:
3 <= n <= 109
代码结果
运行时间: 24 ms, 内存: 15.9 MB
// 题目思路：
// 1. 猴子会发生碰撞的移动方式有多种，这意味着我们需要考虑所有可能的移动组合。
// 2. 对于每个猴子来说，它有两个移动选择：顺时针或逆时针。
// 3. 我们可以使用排列组合来计算所有可能的移动方式，然后计算不发生碰撞的方式数，最后用总方式数减去不发生碰撞的方式数得到碰撞方式数。
// 4. 注意计算过程中需要考虑取模运算，防止结果过大。
import java.util.stream.IntStream;
public class MonkeyCollisionStream {
private static final int MOD = 1000000007;
public static int countCollisions(int n) {
long totalWays = power(2, n, MOD);
long noCollisionWays = 2;
long result = (totalWays - noCollisionWays + MOD) % MOD;
return (int) result;
}
private static long power(long base, int exp, int mod) {
return IntStream.iterate(exp, e -> e > 0, e -> e >> 1)
.mapToLong(e -> {
long res = 1;
if ((e & 1) == 1) res = (res * base) % mod;
base = (base * base) % mod;
return res;
}).reduce(1, (a, b) -> a * b % mod);
}
public static void main(String[] args) {
int n = 4;
System.out.println(countCollisions(n)); // 输出: 14
}
}解释
方法:
这道题目要求计算至少一次碰撞发生的猴子移动方式总数。猴子可以选择向顺时针或逆时针方向移动，因此对于 n 个猴子，每个猴子有两种移动选择，共有 2^n 种可能的移动方式。其中只有两种情况不会发生碰撞：所有猴子都向顺时针移动，或所有猴子都向逆时针移动。题解的思路是首先计算出所有可能的移动方式，然后从中减去这两种不会发生碰撞的情况，余下的即为至少发生一次碰撞的移动方式。
时间复杂度:
O(log n)
空间复杂度:
O(1)
代码细节讲解
🦆
在计算所有猴子移动方式时，为什么只有全顺时针和全逆时针两种情况不会发生碰撞？
▷🦆
题解中提到使用快速幂算法计算2^n，能否详细解释快速幂算法的原理及其为何能提高效率？
▷🦆
在最后计算发生碰撞的移动方式时，为什么要再次对结果进行MOD运算？
▷