Fişierul intrare/ieşire:	swaps.in, swaps.out	Sursă	Algoritmiada 2012, Runda 3
Autor	Paul-Dan Baltescu	Adăugată de	Cezar Mocan •CezarMocan
Timp execuţie pe test	0.3 sec	Limită de memorie	20480 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Swaps

Definim functia f(N, P, A, B) ca fiind probabilitatea ca numarul A sa ajunga pe pozitia B dupa efectuarea a P interschimbari aleatoare de cate doua numere asupra permutarii identice de lungime N. De exemplu, f(3, 1, 1, 2) este egal cu 0.(2), deoarece avem 9 posibilitati de alegere a pozitiilor interschimbate, (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), dintre care doar doua produc rezultatul dorit ((1, 2) si (2, 1)).

Dandu-se T teste de forma N P A B, sa se calculeze pentru fiecare dintre acestea f(N, P, A, B).

Date de intrare

Fişierul de intrare swaps.in va contine pe prima linie numarul natural T. Urmatoarele T linii vor fi de forma N P A B, cu semnificatia din enunt.

Date de ieşire

În fişierul de ieşire swaps.out se vor afla raspunsurile la cele T intrebari, pe linii diferite.

Restricţii

• 1 ≤ N ≤ 1.000.000
• 1 ≤ A, B ≤ N
• 1 ≤ P ≤ 1.000.000
• 1 ≤ T ≤ 100.000
• Rezultatele se vor afisa cu o precizie de 10^-9
• A si B pot sa fie si egale.
• In cazul in care pozitiile alese pentru interschimbare sunt identice, permutarea va ramane la fel pentru pasul urmator.
• Pentru 20% din teste, T ≤ 20, N ≤ 100 si P ≤ 100.
• Pentru alte 20% din teste, T ≤ 20 si P ≤ 100.000.

Exemplu

Cum se trimit solutii?