Matcom Online Grader
Faculty of Mathematics and Computer Science of University of Havana
MOG Round #21Ended |
B - Inversiones
Languages: C, C++, Java, Pascal, Python, Tiger, JavaScript, Haskell, C#
Time & Memory limits: (details)
Si un array $L = \{a_1, a_2, ..., a_n\}$ contiene enteros diferentes, definimos el total de inversiones de $L$ como la cantidad de pares de números que no están ordenados, es decir, la cantidad de índices diferentes $i$, $j$ $(1 \le i \lt j \le n)$ tal que $a_i > a_j$. Para este problema debemos calcular la cantidad de inversiones de las $N!$ permutaciones de los $N$ primeros enteros positivos. Por ejemplo, considere $N = 3$, entonces:
|
Permutación |
Inversiones |
Cantidad de Inversiones |
|
$1, 2, 3$ |
$\{\}$ |
$0$ |
|
$1, 3, 2$ |
$\{(2, 3)\}$ |
$1$ |
|
$2, 1, 3$ |
$\{(1, 2)\}$ |
$1$ |
|
$2, 3, 1$ |
$\{(1, 3), (2, 3)\}$ |
$2$ |
|
$3, 1, 2$ |
$\{(1, 2), (1, 3)\}$ |
$2$ |
|
$3, 2, 1$ |
$\{(1, 2), (1, 3), (2, 3)\}$ |
$3$ |
|
|
$Total = 0+1+1+2+2+3=9$ |
|
Luego para $N = 3$, la respuesta es $9$. Como la solución puede ser inmensa usted solamente calculará la respuesta módulo $987654321$.
Input
Línea 1
: Un único entero $T$ $(1 \le T \le 200)$, la cantidad de casos.
Línea 2… T+1
: Un entero $N$ por línea $(1 \le N \le 1000000)$.
Output
Línea 1…T
: La cantidad de inversiones en las $N!$ permutaciones de los primeros $N$ enteros positivos módulo $987654321$.