Expected Inversions

Points: 12 (partial)

Time limit: 2.0s

Memory limit: 256M

Author:

Problem types

Josh is given an array $a$ $a$ of length $N$ $N$ , where every element is in the range $[1, N]$ $[1, N]$ inclusive. However, some elements are missing and are denoted with the value $0$ $0$ .

Josh, being the innovator he is, decides to randomly assign the missing elements so that the resulting array is a permutation of the first $N$ $N$ positive integers. Your task is to find the expected number of inversions after Josh has finished filling in missing values!

An inversion is defined to be a pair of indices $(i, j)$ $(i, j)$ such that $i < j$ $i < j$ and $a_i > a_j$ $a_{i} > a_{j}$ .

Note: It is guaranteed that there will be at least $1$ $1$ way Josh can fill in the missing elements to result in a permutation of the first $N$ $N$ positive integers.

Constraints

$1 \le N \le 5 \cdot 10^5$ $1 \leq N \leq 5 \cdot 10^{5}$

Subtask 1 [30%]

$1 \le N \le 2 \cdot 10^3$ $1 \leq N \leq 2 \cdot 10^{3}$

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line will contain $N$ $N$ , the length of Josh's array.

The next line will contain $N$ $N$ space-separated integers in the range $[0, N]$ $[0, N]$ , with a value of $0$ $0$ at position $i$ $i$ meaning that the $i^\text{th}$ $i^{th}$ element is missing.

Output Specification

If the answer can be expressed in the form $\frac{P}{Q}$ $\frac{P}{Q}$ , where $P$ $P$ and $Q$ $Q$ are relatively prime, output $PQ^{-1} \pmod{10^9+7}$ $P Q^{- 1} (\mod 10^{9} + 7)$ , where $Q^{-1}$ $Q^{- 1}$ is the modular inverse of $Q$ $Q$ . It is guaranteed that the answer is rational.

Sample Input 1

Copy

5
4 3 0 2 1

Sample Output 1

Copy

Explanation for Sample Output 1

There is only $1$ $1$ way Josh can assign values to missing elements.

The resulting array is $[4, 3, 5, 2, 1]$ $[4, 3, 5, 2, 1]$ and there are $8$ $8$ inversions.

Sample Input 2

Copy

2
0 0

Sample Output 2

Copy

500000004

Explanation for Sample Output 2

There are $2$ $2$ valid arrays, $[1, 2]$ $[1, 2]$ and $[2, 1]$ $[2, 1]$ .

The expected number of inversions is $\frac{1}{2!} + \frac{0}{2!} = \frac{1}{2}$ $\frac{1}{2!} + \frac{0}{2!} = \frac{1}{2}$ . The answer is $1 \cdot 2^{-1}$ $1 \cdot 2^{- 1}$ , the modular inverse of $2$ $2$ is $500\,000\,004$ $500 000 004$ , so the answer is $1 \cdot 500\,000\,004 = 500\,000\,004$ $1 \cdot 500 000 004 = 500 000 004$ .

Sample Input 3

Copy

6
5 0 2 0 1 0

Sample Output 3

Copy

500000013

Explanation for Sample Output 3

There are $6$ $6$ valid arrays, $[5, 3, 2, 4, 1, 6]$ $[5, 3, 2, 4, 1, 6]$ , $[5, 3, 2, 6, 1, 4]$ $[5, 3, 2, 6, 1, 4]$ , $[5, 4, 2, 3, 1, 6]$ $[5, 4, 2, 3, 1, 6]$ , $[5, 4, 2, 6, 1, 3]$ $[5, 4, 2, 6, 1, 3]$ , $[5, 6, 2, 3, 1, 4]$ $[5, 6, 2, 3, 1, 4]$ , $[5, 6, 2, 4, 1, 3]$ $[5, 6, 2, 4, 1, 3]$ .

The expected number of inversions is $\frac{8}{3!} + \frac{9}{3!} + \frac{9}{3!} + \frac{10}{3!} + \frac{10}{3!} + \frac{11}{3!} = \frac{57}{6} = \frac{19}{2}$ $\frac{8}{3!} + \frac{9}{3!} + \frac{9}{3!} + \frac{10}{3!} + \frac{10}{3!} + \frac{11}{3!} = \frac{57}{6} = \frac{19}{2}$ . The answer is $19 \cdot 2^{-1}$ $19 \cdot 2^{- 1}$ , the modular inverse of $2$ $2$ is $500\,000\,004$ $500 000 004$ , so the answer is $(19 \cdot 500\,000\,004) \bmod (10^9+7) = 500\,000\,013$ $(19 \cdot 500 000 004) mod (10^{9} + 7) = 500 000 013$ .

Comments

2

Bolaloon commented on Nov. 29, 2024, 3:34 a.m.

There are testcases without any missing elements.

2

bruce commented on Nov. 29, 2024, 8:55 p.m.

Correct. The problem doesn't guarantee that there are missing numbers. Your code should cover the case.