Problem Description
There is a regular convex polygon with n vertices (n ≥ 3), each hosting one monkey. Every monkey simultaneously moves to one of its two adjacent vertices (clockwise or anticlockwise). A collision occurs if, after the move, two or more monkeys either end up on the same vertex or cross paths on an edge. The task is to count how many possible movement combinations lead to at least one collision, answering modulo 10^9 + 7.
Key Insights
- Total possible move combinations are 2^n because each monkey has 2 choices.
- The only non-collision (safe) moves are when every monkey moves in the same direction (either all clockwise or all anticlockwise).
- Therefore, the number of safe move combinations is exactly 2.
- The answer is then the total combinations minus the safe ones, i.e., 2^n - 2.
- Since n can be very large, use fast modular exponentiation to compute 2^n modulo 10^9 + 7.
Space and Time Complexity
Time Complexity: O(log n) due to fast modular exponentiation.
Space Complexity: O(1)
Solution
We can solve the problem by recognizing that every monkey chooses one of two directions, resulting in 2^n combinations in total. However, to avoid any collision, they must all choose the same direction (either all clockwise or all anticlockwise), which accounts for exactly 2 movements. Thus, the number of ways that cause at least one collision is 2^n - 2. The modulo operation is applied to handle very large numbers. The fast modular exponentiation algorithm (typically available as a built-in function in many languages) ensures that the solution is computed efficiently even for large n.