Count Collisions of Monkeys on a Polygon

Problem Description

In a regular convex polygon with n vertices, each vertex has one monkey that can move to a neighboring vertex. A collision occurs if at least two monkeys end up on the same vertex or intersect on an edge. The task is to return the number of ways the monkeys can move such that at least one collision happens, modulo 10^9 + 7.

Key Insights

• Each monkey can move either clockwise or anticlockwise, resulting in 2^n total movement combinations.
• The only valid movements that result in no collisions are when all monkeys move in the same direction (either all clockwise or all anticlockwise).
• The number of non-collision movements is simply 2, which are the two cases mentioned above.
• Therefore, to find the number of collision scenarios, we can subtract the non-collision cases from the total cases: total movements - non-collision movements.

Space and Time Complexity

Time Complexity: O(1)
Space Complexity: O(1)

Solution

The solution uses a mathematical approach to calculate the total number of ways monkeys can move and the number of non-collision movements. We derive the formula:

1. Calculate the total movements as 2^n.
2. Subtract the non-collision movements (which is 2).
3. Return the result modulo 10^9 + 7.

This approach ensures that we can efficiently compute the result even for large values of n (up to 10^9).

Code Solutions