Problem Statement
A derangement of the set {1, 2, 3, ..., N} is its permutation with no fixed points, i.e., a permutation P such that for all i, P[i] != i.
For example, the set {1, 2, 3} has two derangements: {2, 3, 1} and {3, 1, 2}.
Given is the int N. A bag contains all derangements of the set {1, 2, 3, ..., N}. One derangement is selected from the bag uniformly at random.
Let the selected derangement be P. We can now view P as a sequence of integers and ask the question: what is the minimum number f(P) of swaps we need to make in order to sort P into ascending order?
For example, the optimum solution for P = {4, 3, 2, 1} involves two swaps: e.g., swap 2 and 3, and then swap 1 and 4.
The optimum solution for P = {2, 3, 4, 1} requires three swaps: e.g., swap 1 with 2 (producing {1, 3, 4, 2}), then 2 with 4, and finally 3 with 2.
Let M = 109 + 7. The expected value of f(P) is a rational number. When written as a reduced fraction f(P) = X/Y, Y and M are relatively prime. Return (X * Y-1) modulo M.
Definition
- Class:
- ExpectedValue
- Method:
- solve
- Parameters:
- int
- Returns:
- int
- Method signature:
- int solve(int N)
- (be sure your method is public)
Constraints
- N will be between 2 and 1500, inclusive.
Examples
2
Returns: 1
The only derangement in the bag is P = {2, 1}. We need one swap to sort it, so f(P) = 1. Thus, the expected value of f(P) is 1.3
Returns: 2
As mentioned in the statement, the two derangements in the bag are {2, 3, 1} and {3, 1, 2}. Each of them requires 2 swaps.4
Returns: 666666674
There are 9 derangements for N = 4. Three of them have f(P) = 2, the other six have f(P) = 3. Thus, the expected value of f(P) is (3*2 + 6*3) / 9 = 24/9 = 8/3. Computing modulo M = 1,000,000,007 we have 3-1 = 333,333,336, and (8 * 333,333,336) modulo M = 666,666,674.