== include(page="template/taskheader" task_id="eqprob") ==

Poveste şi cerinţă...

Se da un sir de caractere $S$ de lungime $N$. Se alege la intamplare $A$ un subsir nevid al lui $S$ si $B$ o subsecventa nevida a lui $S$.
Care este probabilitatea ca $A$ si $B$ sa fie egale?

h2. Date de intrare

Fişierul de intrare $eqprob.in$ ...

Fişierul de intrare $eqprob.in$ va contine pe prima linie un numar intreg $T$ reprezentand numarul de teste. Fiecare test are urmatorul format: pe prima linie se afla un numar intreg $N$, lungimea sirului; pe a doua linie se afla sirul $S$.

h2. Date de ieşire

În fişierul de ieşire $eqprob.out$ ...

În fişierul de ieşire $eqprob.out$ se vor afla raspunsurile pentru cele $T$ teste. Raspunsul pentru fiecare test are urmatorul format: un numar real reprezentand probabilitatea ca $A$ si $B$ sa fie egale, afisata cu o precizie de *12 zecimale*.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ T ≤ 10$
* $1 ≤ N ≤ 50$
* $S$ contine doar litere mici ale alfabetului englez.
* Se numeste subsir de lungime $K$ al sirului $S$ un sir $T = S[~i1~]S[~i2~]...S[~iK~]$, astfel incat $1 &le; i[~1~] < i[~2~] < ... < i[~K~] &le; N$.
* Se numeste subsecventa a sirului $S$ un sir $T = S[~i~]S[~i+1~]...S[~j-1~]S[~j~]$, $1 &le; i &le; j &le; N$.
* Doua subsiruri se considera distincte daca cele doua siruri de indici corespunzatoare celor doua subsiruri difera prin cel putin un element. La fel si in cazul subsecventelor.
* Rezultatul va fi considerat corect daca difera fata de rezultatul corect cu cel mult 10^-9^.

h2. Exemplu
table(example). |_. eqprob.in |_. eqprob.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|

|3
1
x
2
aa
3
aca
|1.000000000000
0.555555555556
0.190476190476
|

h3. Explicaţie

...

In testul 2, $S = aa$.

== include(page="template/taskfooter" task_id="eqprob") ==
 

Exista $3$ subsiruri nevide: $a, a, aa$.
Exista $3$ subsecvente nevide: $a, a, aa$.
 
Daca alegem $A = aa$, probabilitatea ca $A = B$ este $1/3$.
Daca alegem $A = a$, probabilitatea ca $A = B$ este $2/3$.
 
Deci, probabilitatea totala este $1/3 * 2/3 + 1/3 * 2/3 + 1/3 * 1/3 = 5/9$.
 
== include(page="template/taskfooter" task_id="eqprob") ==