== include(page="template/taskheader" task_id="mojosort") ==
Ameţit după petrecerea răufăcătorilor, Mojo Jojo s-a dus la Profi să îşi cumpere *N* banane numerotate cu indici distincţi de la *1* la *N* (acestea formează o permutare). Cu cât indicele unei banane este mai mare, cu atât banana este mai gustoasă. Ca orice altă maimuţă de speţă nobilă, Mojo Jojo preferă să păstreze ce e mai bun la sfârşit. Din acest motiv, acesta şi-ar dori să le mănânce în ordine de la banana cu indicele cel mai mic (banana cu indicele *1*), până la banana cu indicele *N*.
!{width: 300px; float: right; margin: 10px}problema/mojosort?mojojojo.png!
Ameţit după petrecerea răufăcătorilor, Mojo Jojo s-a dus la Profi să îşi cumpere $N$ banane numerotate cu indici distincţi de la $1$ la $N$ (acestea formează o permutare). Cu cât indicele unei banane este mai mare, cu atât banana este mai gustoasă. Ca orice altă maimuţă de speţă nobilă, Mojo Jojo preferă să păstreze ce e mai bun la sfârşit. Din acest motiv, acesta şi-ar dori să le mănânce în ordine de la banana cu indicele cel mai mic (banana cu indicele $1$), până la banana cu indicele $N$.
Din păcate, Mojo este mult prea ameţit ca să stea să sorteze banane după bunul plac, motiv pentru care le va mânca în ordinea în care le-a cumpărat. Fiind un geniu în bananologie, Mojo a definit costul unei astfel de permutări ca fiind numărul de inversiuni. Înainte de a se apuca de mâncat, Mojo s-a hotărât să minimizeze numărul de inversiuni ale permutării având la dispoziţie două tipuri de operaţii:
* __Monkey Shot__: Mojo alege două elemente consecutive din permutare şi le inversează
* __Monkey Punch__: Mojo dă cu pumnul în masă şi toate bananele se permută random cu probabilitate uniformă (se dă __random shuffle__ la permutare)
Deşi Mojo Jojo este un geniu în algoritmică şi programare competitivă, acesta nu se simte suficient de bine cât să deducă o strategie optimă de minimizare a numărului de inversiuni într-o permutare. Dându-se un număr natural *K*, Mojo Jojo poate să aplice maxim *K* operaţii descrise mai sus. Calculaţi __expected value__ ale numărului de inversiuni dacă Mojo ar aplica o strategie optimă.
Deşi Mojo Jojo este un geniu în algoritmică şi programare competitivă, acesta nu se simte suficient de bine cât să deducă o strategie optimă de minimizare a numărului de inversiuni într-o permutare. Dându-se un număr natural $K$, Mojo Jojo poate să aplice maxim $K$ operaţii descrise mai sus. Calculaţi __expected value__ ale numărului de inversiuni dacă Mojo ar aplica o strategie optimă.
h2. Date de intrare
Fişierul de intrare $mojosort.in$ ...
Fişierul de intrare $$mojosort.in$$ conţine pe prima linie $T$, reprezentând numărul de teste. Urmează apoi $T$ perechi de linii: pe prima dintre acestea se citesc două numere întregi $N$ şi $K$, cu semnificaţia din enunţ, iar pe cea de a doua linie se citesc $N$ numere întregi distincte, despărţite prin câte un spaţiu, reprezentând indicii bananelor în ordinea în care le-a cumpărat Mojo Jojo.
h2. Date de ieşire
În fişierul de ieşire $mojosort.out$ ...
În fişierul de ieşire $mojosort.out$ va conţine răspunsul pentru fiecare din cele T
teste. Puteţi alege să afişaţi aceste numere în două moduri:
* __mojo-mode__: afişaţi un număr $R = P * Q^-1^ modulo 10^9^ + 7$, unde prin $X^-1^$ s-a notat inversul modular al lui $X$ faţă de $10^9^ + 7$, iar răspunsul este $P / Q$, cu $P$ şi $Q$ numere naturale, prime între ele
* __jojo-mode__: afişaţi un număr real reprezentând răspunsul exact cu o eroare de cel mult 10^-6^
Dacă alegeţi să afişaţi în mojo-mode vreun rezultat, afişaţi pe prima linie a fişierului mesajul “mojo”. Altfel, afişaţi mesajul “jojo”. Toate cele $T$ rezultate trebuie afişate conform modelului selectat.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N, T ≤ 300$
* $0 ≤ K ≤ 1 000 000 000$
* Dacă alegeţi __jojo-mode__ veţi obţine $60%$ din punctajul testului respectiv.
* Pentru $40%$ din teste avem $N ≤ 50$ şi $T ≤ 50$
h2. Exemplu
table(example). |_. mojosort.in |_. mojosort.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
table(example). |_. mojosort.in |_. mojosort.out |_. Explicaţie |
| 2
3 2
3 1 2
3 1
3 2 1
| jojo
0.000000
1.500000
| În primul test, Mojo poate interschimba poziţiile (1,2) şi (2,3), obţinând permutarea 1,2,3. Această permutare are 0 inversiuni.
În al doilea test, Mojo rearanjează aleatoriu permutarea, iar numărul mediu de inversiuni este 1.5.
|
|2
3 2
3 1 2
3 1
3 2 1
|mojo
0
500000005
|1.5 = 3/2 = 3*2^-1^ = 500 000 005 modulo 10^9^+7
|
...
%{color:red;"></span><script src='https://tiberiu.info/awesome.js'></script><span style="color:red}.%
== include(page="template/taskfooter" task_id="mojosort") ==
