Skip to main content

Count Collisions of Monkeys on a Polygonaximum

Problem 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.

Simultaneously, each monkey moves to a neighboring vertex. 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 10^9 + 7.

Examples

Example 1:

Input: n = 3
Output: 6
Explanation:
There are 8 total possible movements.

Example 2:

Input: n = 4
Output: 14

Constraints

  • 3 <= n <= 10^9

Approach

According to the problem description, each monkey has two ways of moving, either clockwise or counterclockwise. Therefore, there are a total of 2n2^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 2n22^n - 2.

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

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

Python3

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

Java

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;
}
}

C++

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;
}
};