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 numerele naturale N si T. Urmatoarele T linii vor contine triplete 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^-6
• 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?