Problem Description
Explanation
To solve this problem, we can realize that the monkeys on a polygon of n vertices will collide if and only if there is at least one vertex with more than one monkey after the movement. We need to count the number of ways the monkeys can move so that at least one collision happens.
We can approach this problem by considering the cases where no collisions happen. If we can count these cases, we can subtract them from the total possible movements to get the number of ways for at least one collision to occur.
To count the cases where no collisions happen, we need to consider the permutations of monkeys such that each monkey is at a different vertex after the movement. This can be calculated using the formula for derangements (permutations without fixed points), which is given by !n = n! * (1 - 1/1! + 1/2! - 1/3! + ... + (-1)^n * 1/n!).
The final answer is then the total possible movements (n^n) minus the number of ways where no collisions happen.
- Time complexity: O(n)
- Space complexity: O(1)
Solutions
class Solution {
public int countCollisions(int n) {
long MOD = 1000000007;
long result = 1;
for (int i = 1; i <= n; i++) {
result = (result * i) % MOD;
}
long derangement = 1;
for (int i = 0; i <= n; i++) {
derangement = (derangement + ((i % 2 == 0) ? 1 : -1) * modInverse(i, MOD)) % MOD;
}
return (int) ((result - derangement + MOD) % MOD);
}
private long modInverse(int x, long MOD) {
if (x == 0) return 1;
long result = 1;
for (int i = 1; i <= x; i++) {
result = (result * i) % MOD;
}
return pow(result, MOD - 2, MOD);
}
private long pow(long x, long y, long MOD) {
long result = 1;
while (y > 0) {
if (y % 2 == 1) {
result = (result * x) % MOD;
}
x = (x * x) % MOD;
y /= 2;
}
return result;
}
}Loading editor...