Fişierul intrare/ieşire:monede2.in, monede2.outSursăInfoPro, Runda 1, Grupa A
AutorTamio-Vesa NakajimaAdăugată deMihaelaCismaruMihaela Cismaru MihaelaCismaru
Timp execuţie pe test3 secLimită de memorie256000 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Monede2

Se considera un sir de N monede numerotate de la 1 la N. La o aruncare, moneda i are probabilitate p[i] sa cada pajura, si 1 - p[i] sa cada cap.

Pentru Q intervale [a, b] se cere sa se afle probabilitatea ca, daca s-ar arunca cu monedele a, a+1, ..., b, un numar impar de monede sa pice pajura.

Date de intrare

Fişierul de intrare monede2.in va contine, pe primul rand, numerele N, Q. Pe urmatoarele N randuri se vor gasi probabilitatile din sirul p. Daca p[i] = x / y, atunci al i-lea rand din acestea va contine perechea x y. Pe urmatoarele Q randuri se vor gasi perechi a b, indexate de la 1, dintre care fiecare reprezinta o interogare.

Date de ieşire

În fişierul de ieşire monede2.out se vor afisa raspunsurile la cele Q interogari. Daca raspunsul este x / y, se vor afisa oricare numere p q unde q este nenul, si x * q = y * p (mod 1.000.000.007).

Restricţii

  • 1 ≤ N ≤ 1.000.000
  • 1 ≤ Q ≤ 1.000.000
  • 1 ≤ x, y < 1.000.000.007
  • Pentru 23 de puncte, N ≤ 15, Q ≤ 100.
  • Pentru alte 10 puncte, N, Q ≤ 1.000.
  • Pentru alte 37 puncte, N, Q ≤ 200.000.
  • Pentru alte 15 puncte, p[i] este diferit de 1 / 2.

Exemplu

monede2.inmonede2.out
3 6
1 4
1 3
1 2
1 1
1 2
1 3
2 2
2 3
3 3
1 4
5 12
1 2
1 3
1 2
1 2
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?