Question

2550. Count Collisions of Monkeys on a Polygon

中文文档

Description

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) % n in the clockwise direction, or
• the vertex (i - 1 + n) % n in 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

Solutions

Solution 1: Mathematics (Fast Power)

According to the problem description, each monkey has two ways of moving, either clockwise or counterclockwise. Therefore, there are a total of $2^n$ ways to move. The non-collision ways of moving are only two, that is, all monkeys move clockwise or all monkeys move counterclockwise. Therefore, the number of collision ways of moving is $2^n - 2$.

We can use fast power to calculate the value of $2^n$, then use $2^n - 2$ to calculate the number of collision ways of moving, and finally take the remainder of $10^9 + 7$.

The time complexity is $O(\log n)$, where $n$ is the number of monkeys. The space complexity is $O(1)$.

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

class Solution {
  public int monkeyMove(int n) {
    final int mod = (int) 1e9 + 7;
    return (qpow(2, n, mod) - 2 + mod) % mod;
  }

  private int qpow(long a, int n, int mod) {
    long ans = 1;
    for (; n > 0; n >>= 1) {
      if ((n & 1) == 1) {
        ans = ans * a % mod;
      }
      a = a * a % mod;
    }
    return (int) ans;
  }
}

class Solution {
public:
  int monkeyMove(int n) {
    const int mod = 1e9 + 7;
    using ll = long long;
    auto qpow = [&](ll a, int n) {
      ll ans = 1;
      for (; n; n >>= 1) {
        if (n & 1) {
          ans = ans * a % mod;
        }
        a = a * a % mod;
      }
      return ans;
    };
    return (qpow(2, n) - 2 + mod) % mod;
  }
};

func monkeyMove(n int) int {
  const mod = 1e9 + 7
  qpow := func(a, n int) int {
    ans := 1
    for ; n > 0; n >>= 1 {
      if n&1 == 1 {
        ans = ans * a % mod
      }
      a = a * a % mod
    }
    return ans
  }
  return (qpow(2, n) - 2 + mod) % mod
}

function monkeyMove(n: number): number {
  const mod = 10 ** 9 + 7;
  const qpow = (a: number, n: number): number => {
    let ans = 1n;
    for (; n; n >>>= 1) {
      if (n & 1) {
        ans = (ans * BigInt(a)) % BigInt(mod);
      }
      a = Number((BigInt(a) * BigInt(a)) % BigInt(mod));
    }
    return Number(ans);
  };
  return (qpow(2, n) - 2 + mod) % mod;
}